[실버5]백준 1181번(단어 정렬) - 코테공부 40일차(2025.03.06)

문제유형

정렬

풀이 방법 도출 과정

1. 알파벳 소문자로 이루어진 N개의 단어가 들어오면 "길이가 짧은 것부터", "길이가 같으면 사전 순으로" 우선순위 대로 정렬하는 것이 문제이다.

2. 입력은 첫째줄에 얼마정도 나타나는 지(N) 나머지는 정렬할 대상이 온다. N은 20000만 이하, 문자열의 길이는 50을 넘지 않음

3. sort 알고리즘을 쓰며, lambda함수를 사용하여 정렬을 해보도록 하겠다.

시간 복잡도

시간 복잡도는 O(N)이다. 시간복잡도가 최악이 될 경우 2만이기에 시간복잡도 부분에서 안정하다. 

코드 및 간단설명

정렬을 사용하여 고쳐보았다. 

N = int(input())
result = set()  # 중복 제거를 위해 set 사용

for i in range(N):
    A = input()
    result.add(A)  # 중복 제거하면서 저장

result = sorted(result, key=lambda x: (len(x), x))  # 길이순 + 사전순 정렬

for item in result:
    print(item)

이보다 더 좋은 코드가 있지만 sys를 사용하고 for 함수를 한줄로 적는 방식을 사용하였기에 서술하지 않겠다.