글 읽기 - 로직의 문제일까요 파이썬의 속도 문제일까요

whilescape 4년 전 0

질문 있습니다.

시간초과 메시지가 뜬다는 것은 일단 코드는 잘 작동한다는 것이죠?

permutation을 어떻게 처리하느냐가 이 문제의 관건이라고 개인적으로 생각하는데요

저는 heap's algorithm을 기반으로한 permutation generator를 참조하여 사용하였습니다. (파이썬에 yield 이런 게 있는지 처음 알았네요, 공부ㄱㄱ)

최소한의 interchange를 거쳐 다음 permutation을 generate하는 알고리즘이라고 들어서, 제가 직접 작성한 perm-gen 함수보다는 좋은 것 같습니다.

그렇지만 이걸 사용해도 시간초과 메시지는 피해갈 수 없네요

이전의 시도 :

1) itertools를 이용하여 미리 permutation 리스트를 만들어 둠. >> 메모리 초과 오류

2) 직접 작성한 permutation generator (대소비교를 통한 next permutation을 반환하는 함수) 사용 >> 시간초과

3) 아래 코드

이 아래 코드에서 효율성을 높일 수 있는 부분이 어디 있을까요? 고수님들 평가 부탁드립니다.

아 is_groupword 함수의 효율성부터 다시 확인해볼게요

def permutation_generator(a):
    n = len(a)
    c = [0]*n
    A = list(a)
    yield A
    i = 1
    while i < n:
        if c[i] < i:
            if i % 2 == 0:
                temp = A[0]
                A[0] = A[i]
                A[i] = temp
            else:
                temp = A[c[i]]
                A[c[i]] = A[i]
                A[i] = temp
            yield A
            c[i] += 1
            i = 1
        else:
            c[i] = 0
            i += 1

def is_groupword(w):
    dic = {}
    pi = -1
    for i in range(len(w)):
        if w[i] in dic.keys():
            if pi >= 0 and w[i] != w[pi]:
                return False
        else:
            dic[w[i]] = 0
        pi = i
    return True
    
def solution():
    import sys
    n = int(sys.stdin.readline())
    part = []
    for _ in range(n):
        part.append(sys.stdin.readline())
    answer = [] 
    perm = permutation_generator([e for e in range(n)])
    for p in perm:
        temp = ""
        escape = 0
        for idx in p:
            temp += part[idx]
            if is_groupword(temp) != True:
                escape = 1
                break
        if escape == 0:
            answer.append(temp)
        if len(answer) > 1:
            sys.stdout.write('-_-'+'\n')
            return
    if len(answer) == 0:
        sys.stdout.write('gg'+'\n')
        return
    sys.stdout.write(answer[0]+'\n')
    
    
solution()

댓글을 작성하려면 로그인해야 합니다.