[Python/백준] #1062 - [가르침] [try_again]

[가르침]-1062번

1062번: 가르침

Another answer

from itertools import combinations
n, k = map(int, input().split())
alpha = {'b': 20, 'd': 19, 'e': 18, 'f': 17, 'g': 16, 'h': 15, 'j': 14,
            'k': 13, 'l': 12, 'm': 11, 'o': 10, 'p': 9, 'q': 8, 'r': 7,
            's': 6, 'u': 5, 'v': 4, 'w': 3, 'x': 2, 'y': 1, 'z': 0}
#각 문자에 비트마스킹을 하기위해 값을 매칭시켜둠 

if k < 5: #배울 수 있는 단어가 총 5개도 안되면 기본 단어도 못배우니까 0출력
    print(0)
else:
    k -= 5 #k에서 기본단어 개수 5개 미리 제외
    nece_chars = {'a', 'n', 't', 'i', 'c'}
    input_chars = []
    cnt = 0
    for _ in range(n):
        tmp = 0
        for c in set(input())-nece_chars: #입력받은 단어에서 필수(a,n,t,i,c)를 제외한 것중
            #print(alpha)
            tmp |= (1 << alpha[c])
        input_chars.append(tmp)
        #print(input_chars) 배워야 할 모든 문자를 비트연산자로 하나의 십진수로 표현해둠 
    power_by_2 = (2**i for i in range(21)) # 2의n승 중에 알파벳26개에서 5개를 제외한 21개에서 모든 조합을 뽑음 
    for comb in combinations(power_by_2, k):
        test = sum(comb)
        ct = 0
        for cb in input_chars:
            if test & cb == cb: #만든 조합이 우리가 필요한 글자에 있으면 ct올림 
                ct += 1
        cnt = max(cnt, ct)
    print(cnt)

무려 3일을 고생했는데 못풀어서 결국 구글링을 해서 풀었다. 답 베끼는 것만 1시간30분이 넘게 걸렸다 ㅋㅋ..

우선 나는 내가 어떤 알고리즘을 쓰는지도 모르고 그냥 하나하나 반례가 나오면 반례 해결하는데만 급급해서 막짰는데, 코드가 맞았는지 틀렸는지도 모르겠다. 계속 시간초과or메모리초과가 났다. 검새개보니 원래 이 문제 자체가 메모리나 시간초과가 잘 난다고 하더라. 검색을 해보니 이 문제를 푸는데 필요한 알고리즘은 비트마스킹 이었다. 알고리즘 자체도 처음 들어봤고, 이해하는데만 시간이 오래걸렸다. 비트마스킹의 자세한 설명은 마이구미님의블로그 를 참조했다. 또한 저 코드 자체는 coder38611님의 블로그를 베껴왔다. 코드의 설명은 주석에 추가해놨다.

몇일동안 이 문제를 풀면서 느끼점은 나는 알고리즘의 중요성을 못느끼고 그냥 내가 어떻게든 이 문제를 해결하면 되지 않는가라는 생각을 했었는데, 그렇게 짜면 반례?오류도 많이 생기고 시간초과,메모리 초과등 효율성이 매우 떨어진다는 것을 알게되었다. 문제를 풀면서 따로 알고리즘들만 공부하는 것도 생각해봐야겠다.