요즘 정렬 문제 풀 때마다 뿌듯하다. 한 번에 맞기 때문임 ㅎ
물론 삽입, 버블, 병합 정렬 등등등의 다양한 알고리즘에 대해 확실하게 알지는 못하지만 (?)
여튼 오늘의 문제도 성공적으로 풀었다!

1181: 단어 정렬

1. 첫 번째 풀이: 성공

이번 문제는 조금 고민을 했는데 솔직히 왜 했는지 모르겠음. 아니 알지 정확히는... 내가 바보거든... 여튼 문제 풀이를 공유해보자면,

# 길이가 짧은 것부터 ㅇ
# 길이가 같으면 사전 순으로 ㅇ
# 중복 불허 ㅇ

import sys
N = int(sys.stdin.readline())

words = []
for _ in range(N):
    words.append(sys.stdin.readline().strip())

words.sort(key=lambda x: (len(x), x))

# answer = set(words) - 실패

answer = []
for i in range(N):
    if words[i] in answer:
        continue
    else:
        answer.append(words[i])
for word in answer:
    print(word)

앞으로 위에 저렇게 조건을 정리해둬야겠다...! 확실히 정리하니까 눈에 확확 잘 들어오면서 처리해야 할 부분들이 잘 보이는 듯하다. 일단 풀이 순서는,

1. 단어 숫자 받고,
2. 리스트에 단어 추가하고,
3. 정렬하고,
4. 중복 제거 하고,
5. 하나씩 출력하기

이다. 다른 부분은 이전 문제의 풀이와 유사하거나 크게 다를 게 없는데, 중복 제거 부분이 풀면서도 마음에 걸렸다. 또 시간초과나 메모리 초과 걸릴까봐... 여튼 일단은 무사히 통과!

2. 두 번째 풀이: 성공

사실 두 번째 풀이는 velog를 쓰기까지 없었다. 그런데 set을 쓰는 부분이 왜 틀렸는지 생각하면서 인터넷을 보다가,

이것이 생각난 것이다...!
이전 문제 풀이에서 중복 제거 부분이 마음에 걸린다고 하였는데, 이 중복 제거 부분을 !!! set이 해결해줄 수 있겠다~ 하고 새로 풀어보았다.

import sys
N = int(sys.stdin.readline())

words = set()
for _ in range(N):
    words.add(sys.stdin.readline().strip())

words = list(words)
words.sort(key=lambda x: (len(x), x))

for word in words:
    print(word)

그 결과는...

시간 측면에서 확실히 줄어들었다! 그런데 공간 복잡도 측면에서는 for 문을 덜 쓰니까 메모리가 덜 쓰일 거라 생각했는데 오히려 더 쓰여서 놀랐다. 인터넷에 찾아봐도 명확한 답이 없어서 이건 좀 더 알아보아야 할 것 같다.

사실 이 풀이가 생각난 이유가 set에 append를 할 수 없고 set에는 sort 메소드가 없다는 부분이었다.
그럼 add를 사용해서 set을 사용할 수 있게 하고 이를 다시 list로 변환해서 sort를 한다면...? 이라는 아이디어... 크...

3. 다른 풀이

인터넷의 다른 풀이들을 찾아봤을 때 전반적으로 흘러가는 과정들은 비슷해서 새롭게 알게 된 사실만 정리!

• sys.stdin.readline()은 input()에 비해 빠르지만, /n을 포함하고 있으므로 꼭 strip()과 함께 써줘야 한다.
• words.sort(key=lambda x: (len(x), x)) 이 부분에서 len(x)가 아닌 len만 써줘도 (만일 뒤에 x를 안 쓸 거면) 길이에 따라 배열이 된다!

오늘도 신기한 알고리즘의 세계 끝!