더북(TheBook)

전체 코드

4장/튜플.py

def solution(s):
    data = s[2:-2].split("},{")
    data = sorted(data, key=lambda x: len(x))
    answer = []
    for item in data:
        item = list(map(int, item.split(",")))
        for value in item:
            if value not in answer:
                answer.append(value)
    return answer

제출한 후 결과를 보면 정답은 맞지만, 백만 개 데이터에 0.28초 가량이 소요되었다는 사실을 알 수 있습니다. 현재 프로그램의 시간 복잡도가 O(nlogn)이라는 것을 감안해도 필요 이상으로 오래 걸립니다. 파이썬의 정렬은 팀 정렬(tim sort) 알고리즘에2 기반하므로 10만 개 데이터 기준 약 0.01초가 걸리기 때문에 아무리 늦어도 0.02초 정도여야 정상입니다.

테스트 12 > 통과 (261.79ms, 12MB)
테스트 13 > 통과 (282.88ms, 12.1MB)
테스트 14 > 통과 (262.97ms, 11.9MB)

즉, 예상한 결과보다 약 10배 이상의 시간이 소요됐습니다. 이 정도의 알고리즘이면 O(n2) 수준으로, 작동에는 문제가 없으나 개선이 필요한 상태입니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.