1020 디지털 카운터 python 이해쉽지만 구현많은 풀이

문제

https://www.acmicpc.net/problem/1020

1020번: 디지털 카운터

아이디어

15자리라니 상상도 못할 큰 수가 들어온다.

1. N자리 수를 a,b,c,...번쨰에서 잘라낸 조각을 A,B,C,... 라고 할 때,

N자리 수의 선분 개수는 선분개수(A)+선분개수(B)+선분개수(C)+....와 같다.

즉 우리들은 어느정도 계산가능한 자릿수로 15자리이하의 숫자를 잘라버릴 수 있다.

2. 3,4,5,6,7개의 선분이 수 한자리를 나타내는데 사용된다.

두자리는 3+3~7+7 -> 6~14개의 선분이 사용될 것이다. (11개)

음 그럼 3자리,4자리,...어느정도 자릿수까지는 사용되는 선분 수 종류가 그리 크지 않을 것 같다.

실험을 해보자.

우리들은 0이상 10 ** 적당한 자릿 수 미만의 숫자를 보면서, 각 숫자의 선분을 계산하고 그 결과를

저장하면 될 것이다. 

단 0을 앞에서 채워주는 경우도 있으므로 그걸 빼먹으면 안된다.

이를 어떻게 활용하나면

특정한 수가 선분 몇개인지 알려주는 배열을 사용하는 것이 아니라

key는 특정한 선분 개수, value는 그 선분 개수인 수들을 담고있는 배열

이런 hash table을 사용하는 것이다.(스포하자면 배열도 가능할 것 같으나... 굳이 쓸 이유는 없을 것 같다.)

strline = {'0': 6, '1': 2, '2': 5, '3': 5, '4': 4, '5': 5, '6': 6, '7': 3, '8': 7, '9': 5}  # 각 숫자의 선분 개수


def compute(s):  # 문자열의 선분 개수를 리턴함
    result = 0
    for ss in s:
        result += strline[ss]
    return result


X = 5  # 적다한 자릿 수
dic = {}  # dic[x][value]: x자릿수에서 선분갯수가 value인 수를 담은 리스트
for zari in range(1, X + 1):
    dic[zari] = {}
for num in range(10 ** X):
    s = str(num)
    l = len(s)  # num 문자열의 길이
    ref = compute(s)
    if ref not in dic[l]:
        dic[l][ref] = [num]
    else:
        dic[l][ref].append(num)
    for i in range(1, X - l + 1):  # 앞에서 0을 채워주는 경우
        new = ref + i * 6
        if new in dic[l + i]:
            dic[l + i][new].append(num)
        else:
            dic[l + i][new] = [num]
for zari in range(1, X + 1): # 각 자리별로 나올 수 있는 선분개수가 몇종류 있는 지
    print(zari, len(dic[zari]))

위 코드를 돌려보면 생각보다 더 적을 것이다. (X는 취향 껏 정해주면 된다.)

단 나의 경우엔 X를 5로 잡았다.

왜냐하면 

N이 15자리가 들어온다 하면 2조각(8자리,7자리)으로 나눈다면 분명 백준 서버가 고통받다가 시간초과를 내뱉을 것이므로 최소 3조각으로 나눌 수 밖에 없을 것이다.

15/3 = 5이므로 5자리로 잡았다.

더 적은 자리수로 하면 4조각으로 나눠야하고 더 많은 자리수로하면 채점시간과 디버깅시간만 늘어날 뿐이다. 오래걸려서... 빨리빨리 틀린거 있음 고쳐주고 다시 풀고 그러는게 최고다.

 

풀이

dic[zari][value]는 zari 자릿수에서 선분개수가 value인 수들을 담고 있는 배열이다.

만약 우리가 조각으로 안나눴을 때 풀이는

my를 입력으로 들어온 수, ref를 my의 선분개수,N을 my의 자릿수라 할때

ref와 선분개수가 같은 모든 수를 다 담고 정렬한걸 tmp라 하자.

우리가 궁금한건 my다음의 수와 my의 차이이다.

찾은수 - my가 원하는 값이 될 것이다.

단 my가 tmp에서 가장 큰 수일수도 있다. 그럼 카운터가 000...000으로 초기화되고 tmp[0]와의 차이를 구해야한다.

이는 간단하게 tmp[0] + 10**my자릿수 - my를 계산하면 된다.

이 풀이를 최적화해보자.

우선 순서가 필요해보이므로 다 정렬해보자 (내 추측으론 0부터 숫자를 순회해 dic을 만들었으므로 이미 정렬돼있을거 같기도 한데... 귀찮은 상황 만들기 싫어서 그냥 정렬했다.)

for i in range(1, 6):
    for j in dic[i].keys():
        dic[i][j].sort()

case를 나눠야한다

N이 my의 자릿수라 할때

1. N <= 5

2. N <= 10

3. N <= 15

각 케이스를 계산해보자.

1번 케이스

dic에서 그냥 찾으면 된다.

우선 dic[N][ref]를 보자.

우리가 수들을 하나하나 비교하는건 비효율적인 것 같다. my 다음에 있는 수가 몇인지만 궁금하다.

upperbound로 O(log(len(dic[N][ref]))만에 빠르고 간단하게 찾을 수 있다.

이진탐색 3형제 코드링크이다.

여기서 우리는 우리가 원하는 결과(배열범위를 벗어났거나 해당하는 수가 없음)에서 -1을 리턴해줘서 구현할 때 조금이라도 더 편하게 처리를 해주면 된다. (각자만의 예외처리 방법이 있다면 그걸 써보자)

미리 말하자면 lower bound는 안쓰인다. 풀이를 보면서 생각해보자

pythonAlgorithm/binarysearch.py at master · nayounsang/pythonAlgorithm · GitHub

GitHub - nayounsang/pythonAlgorithm: Algorithm template code with python.

단 my가 dic[N][ref]에서 제일 큰 수 일수도 있다. 그래서 dic[N][ref][0]와도 비교해줘야한다.

if N <= 5:
    ans = 10 ** N + dic[N][ref][0] - int(my)
    idx = ub(0, len(dic[N][ref]), dic[N][ref], int(my))
    if idx != -1:
        ans = min(ans, dic[N][ref][idx] - int(my))
    print(ans)
    sys.exit()

ub가 upperbound이다. 

ub가 리턴하는 값이 len(dic[N][ref]) 이상이라면(같다면) 그 다음 수가 없단 의미므로 -1을 리턴하게 해줬다.

나머진 목표로 하는 인덱스를 리턴한다.

 

2번 케이스

2 조각으로 나눠야한다.

5자리 조각 + N-5자리 조각으로 나눠질 것이다.

5자리에서 나올 수 있는 선분개수 + N-5자리에서 나올 수 있는 선분개수 = ref인 것만 관심이 있다.

경우가 3가지가 나온다.

1. 000..00으로 초기화 된 이후를 보는 경우(1번 케이스의 dic[zari][ref][0]와 같다.)

2. 앞의 5자리까진 동일하지만 뒤의 N-5자리가 my 뒤의 N-5자리 보다 큰 경우

3. 앞의 5자리가 my 앞 5자리보다 큰 경우

1번은 그냥 구해주면 되고,

2번은 우선 동일한 것을 찾아야하므로 binary search를 써야한다.

만약동일한 것이 없다면 -1을 리턴해준다.

동일한 앞조각이 존재한다면 뒷조각은 upper bound로 찾아준다.

 3번은 앞조각에 대해 upper bound로 찾아준다.

뒷조각은 가능한 경우중 제일 적은 값(배열에서 인덱스가 0인 수)을 취해줘야한다. 어차피 앞조각이 my보다 크다면 뒷조각을 붙여 만들 수 있는 수들은 다 my보다 클 것이기에...

def adjust(cap, num): # 특정 숫자에 cap만큼 0을 뒤에 이어줌
    return num * (10 ** cap)
    
    
if N <= 10:
    front = my[:5] # 앞의 5자리 조각
    back = my[5:] # 뒤의 N-5자리 조각
    case1, case2, case3 = 10 ** N, 10 ** N, 10 ** N
    # case1: 000..000으로 초기화 된 이후의 경우 
    # case2: front가 같고 back이 my[5:]보다 큰 경우
    # case3: front가 my[:5]보다 큰 경우
    for k1 in dic[5].keys():
        for k2 in dic[N - 5].keys():
            if k1 + k2 != ref: # 우린 선분개수가 같은 것만 관심 있음
                continue
            case1 = min(case1, 10 ** N + adjust(N - 5, dic[5][k1][0]) + dic[N - 5][k2][0] - int(my))
            idx = bns(0, len(dic[5][k1]) - 1, dic[5][k1], int(front)) 
            if idx != -1:
                idx2 = ub(0, len(dic[N - 5][k2]), dic[N - 5][k2], int(back))
                if idx2 != -1:
                    case2 = min(case2, adjust(N - 5, dic[5][k1][idx]) + dic[N - 5][k2][idx2] - int(my))
            idx = ub(0, len(dic[5][k1]), dic[5][k1], int(front))
            if idx != -1:
                case3 = min(case3, adjust(N - 5, dic[5][k1][idx]) + dic[N - 5][k2][0] - int(my))
    print(min((case1, case2, case3)))
    sys.exit()

당연히 가능한 경우중 최소를 구해야한다. 

 

 

3번 케이스

조각을 front(앞의 5조각) middle(중간 5조각) back(뒤의 N-10조각) 으로 나눌 것이다.

우리는 다음과 같은 경우를 처리해야한다.

1. 000...00으로 초기화 된 이후의 경우

2. 앞5자리가 front와 같고 중간5자리가 middle과 같고 뒤 N-10자리가 back보다 큰 경우

3. 앞5자리가 front와 같고 중간5자리가 middle보다 크고 뒤 N-10자리가 가능한 경우중 가장 작은 수인 경우

4. 앞5자리가 front보다 크고 중간5자리와 뒤 N-10자리가 가능한 경우 중 가장 작은 수인 경우

2번 케이스를이해했다면 구현해 볼 수 있을 것이다.

직접 구현해보고 안되면 제 스파게티 코드를 선물해드립니다...ㅠㅠ

front = my[:5]
middle = my[5:10]
back = my[10:]
case1, case2, case3, case4 = 10 ** N, 10 ** N, 10 ** N, 10 ** N
for k1 in dic[5].keys():
    for k2 in dic[5].keys():
        for k3 in dic[N - 10].keys():
            
            if k1 + k2 + k3 != ref:
                continue
            num1 = adjust(N - 5, dic[5][k1][0]) + adjust(N - 10, dic[5][k2][0]) + dic[N - 10][k3][0]
            
            case1 = min(case1, num1 + 10 ** N - int(my))
            idx1 = bns(0, len(dic[5][k1]) - 1, dic[5][k1], int(front))
            if idx1 != -1:
                idx2 = bns(0, len(dic[5][k2]) - 1, dic[5][k2], int(middle))
                if idx2 != -1:
                    idx3 = ub(0, len(dic[N - 10][k3]), dic[N - 10][k3], int(back))
                    if idx3 != -1:
                        num2 = adjust(N - 5, dic[5][k1][idx1]) + adjust(N - 10, dic[5][k2][idx2]) + dic[N - 10][k3][
                            idx3]
                        case2 = min(case2, num2 - int(my))
                        
                idx2 = ub(0, len(dic[5][k2]), dic[5][k2], int(middle))
                if idx2 != -1:
                    num3 = adjust(N - 5, dic[5][k1][idx1]) + adjust(N - 10, dic[5][k2][idx2]) + dic[N - 10][k3][0]
                    case3 = min(case3, num3 - int(my))
                    
            idx1 = ub(0, len(dic[5][k1]), dic[5][k1], int(front))
            if idx1 != -1:
                num4 = adjust(N - 5, dic[5][k1][idx1]) + adjust(N - 10, dic[5][k2][0]) + dic[N - 10][k3][0]
                case4 = min(case4, num4 - int(my))
                
          

print(min((case1, case2, case3, case4)))

 

결론

dp테이블을 짤 것도 없이, 그냥 가능한 경우를 모두 다 찾아버리는 거다. 이 중 최적의 해를 구한다.

각 자릿수별로 나오는 선분개수 종류가 적어서 가능한 일이다.

실험을 통해서 우리가 풀이를 할 수 있을 정도로 적은 종류,범위를 가진 데이터를 뽑아내는 것이 중요하다.

그것을 기준으로 풀이를 해보고....

(사실 복잡도 분석이 잘 안되는 문제를 풀때 많이 그럴 것이다. 적당한 input을 넣고 그것이 얼마나 계산하는지 출력해보고)

풀이시간도 무척이나 빠를 것이다.

케이스를 세세히 나눠 구현을 어떻게든 하는 능력, 이분탐색을 응용하는 능력이 필요하다.

둘다 골드정도 티어에서 많이 다뤄진 주제이다.

이분탐색의 log복잡도는 풀이가 도저히 생각 안날때 우리를 구해주는 경우가 상당히 많은 것 같다.