코드

input() 활용

n = int(input())
list_ = []

for _ in range(n):
    list_.append(input())

# 중복 제거
ls = list(set(list_))

# 리스트 정렬 후 길이 별로 정렬
ls.sort()
ls.sort(key=len)

# 선택 정렬 => 시간 초과
# for i in range(len(ls)-1):
#     for j in range(i, len(ls)-1):
#         if(len(ls[i]) == len(ls[j+1])):
#             if(ls[i] > ls[j+1]):
#                 ls[i], ls[j+1] = ls[j+1], ls[i]
#                 break

for i in ls:
    print(i)

sys.stdin.readline() 활용

import sys
# input()보다 속도 면에서 우수
n = int(sys.stdin.readline())
list_ = []

for _ in range(n):
    # 한 줄 단위로 입력받기 때문에 개행문자가 같이 입력 받아짐 => strip()으로 제거
    list_.append(sys.stdin.readline().strip())
    
ls = list(set(list_))

# 리스트를 길이 별로 정렬
ls.sort()
ls.sort(key=len)

for i in ls:
    print(i)

문제 해설

파이썬 기본 정렬 라이브러리를 사용하지 않고 선택 정렬을 직접 구현하니 시간 초과가 발생하였다. 알고리즘 문제를 풀 때 시간 복잡도를 제어하는 것이 중요하다는 것을 또 한 번 깨달았다.

파이썬 기본 정렬 라이브러리는 병합 + 삽입 정렬의 하이브리드 방식으로 동작하여 최악의 경우에도 O(NlogN)을 보장하여 선택 정렬(시간 복잡도 : O(N**2))보다 더 빠른 성능을 보여준다

또한 시간을 더 단축하기 위하여 input() 대신 sys.stdin.readline()을 활용하여 답안도 작성하였다

댓글남기기

참고