(Python) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

풀이

arr = []
for _ in range(int(input())):
    m = input()
    if m in arr:
        continue
    if len(arr) == 0:
        arr.append(m)
    for i in range(len(arr)):
        if len(arr[i]) > len(m):
            arr.insert(i, m)
            break
        elif len(arr[i]) == len(m):
            if arr[i] > m:
                arr.insert(i, m)
                break
    if m not in arr:
        arr.append(m)

for i in arr:
    print(i)

 

처음엔 위와 같이 in, len()과 비교 연산 등을 사용하여 문제를 풀려했으나 시간 초과가 발생하였다. O(n²)의 비교 연산을 여러 번 수행하기 때문이라고 생각해 python의 sort를 사용해보았다.

s = set([])
for _ in range(int(input())):
    m = input()
    s.add(m)
s = list(s)
s.sort()
s.sort(key=len, reverse=False)

for i in s:
    print(i)

 

일단 set을 활용하여 중복되는 값이 들어가지 않도록 하였고, 그 후 set을 리스트로 변환하였다.

첫번째 sort에선 문제의 요구사항대로 사전순으로 정렬하였고,  두번째 sort에서는 key로 len을 사용하여 글자 수가 짧은 순서대로 정렬하였다.