백준 1181번- '단어 정렬' (PYTHON 풀이)

문제:

 

사용자로부터 입력 개수를 받은 뒤 그 수만큼 소문자 단어를 받는데, 이를 글자 수 기준으로 정렬하고, 같은 경우 사전 기준대로 순서대로 놓고 전부 출력하면 되는 문제이다.

 

풀이:

N = int(input())
li = []


for i in range(N):
    k = input()
    li.append(k)
    for j in range(i):
        if len(li[i]) < len(li[j]) or len(li[i]) == len(li[j]) and li[i] < li[j]:
            li[i], li[j] = li[j], li[i]

print(li)

처음에는 이렇게 풀었다. 조금 복잡하긴 하지만 비쥬얼스튜디오코드에서 실행했을 때 이상 없이 잘 되어서 제출했는데 역시나 시간초과가 떴다.

아무래도 이 코드는 최대 O(n^2)에 해당하는 시간 복잡도를 가지고 있기 때문에 큰 수를 입력 받게 될 경우 엄청나게 오래 걸리게 될 것이다. 최근에 파이썬 내장 함수를 활용해서 많이 풀었어서 이번엔 내장 함수 활용을 하지 않고 풀려고 하다 보니 길어졌는데 시간 초과가 나오니 어떻게 풀어야할지 감이 안왔다.

N = int(input())
li = []


for i in range(N):
    k = input()
    li.append(k)

li.sort()
li.sort(key=len)

print("\n".join(li))

그래서 결국 내장 함수를 활용하기로 했는데, 서치하다가 sort의 key를 정해서 이를 기준으로 정렬할 수 있는 것을 발견하였다.

그래서 위와 같이 풀었는데 틀렸다고 나와서 문제를 다시 읽어보았다. 

문제에서는 '단, 중복된 단어는 하나만 남기고 제거해야 한다.'는 내용이 있었다. 내 코드는 중복된 단어를 제거하는 코드가 없어서 틀린 것 같았다. 그래서 이를 추가하였다.

 

최종 코드:

N = int(input())
li = []


for i in range(N):
    k = input()
    li.append(k)

li = list(set(li))
li.sort()
li.sort(key=len)

print("\n".join(li))

이렇게 푸니 정답이라고 나왔다.

set 함수를 활용해서 중복을 제거하고 이를 알파벳 순서대로 sort로 정렬한 뒤에, 앞서 말한 key를 활용해서 1차로 알파벳 순서 정렬된 리스트를 길이로 또 한번 조건을 걸어 정렬해준다. 마지막으로는 출력 결과와 동일하게 하기 위해 join 함수를 통해 띄어쓰기로 출력하게 만든다.

.

.

역시 파이썬은 간단하다 ..^^