파이썬 Python | 알고리즘 | 백준 단어 정렬

⭕ 파이썬 Python | 알고리즘 | 백준 단어 정렬

➡️ 문제링크

• https://www.acmicpc.net/problem/1181

 

➡️ 문제 탐색하기

• 우선, 몇 개의 단어를 처리할지를 미리 알아야 하기 때문에 단어의 개수를 먼저 입력받는 것이 필요하다. 
• 처음에는 단어를 리스트에 저장하려 했으나, 문제 조건에서 중복을 제거하라는 것을 보고 set을 사용하도록 변경했다. set은 중복을 자동으로 제거하는 특성이 있다. 따라서, 단어를 하나의 리스트에 저장하는 대신, 중복된 단어를 제거하기 위해 set을 사용한다. set에 원소 하나를 추가하는 시간복잡도는 O(1)이다. N개의 단어들을 set에 넣어야 하므로 , 총 시간복잡도는 O(N)이다. N은 최대 20,000개로 연산 20,000번은 시간 2초내에 충분히 가능한 연산 개수이다.
• https://80000coding.oopy.io/642d8efd-0cd0-40f4-92ce-55a7896e7a44
• 최종적으로 "길이가 짧은 것부터, 길이가 같으면 사전 순으로" 조건을 만족하도록 사전 순으로 먼저 정렬하고, 길이 순으로 정렬한다.

Python 내장 자료구조의 시간복잡도

 

 

➡️ 코드 설계하기

• 빠른 입출력을 위해 sys.stdin.readline()을 사용하여 입력을 받는다. sys.stdin.readline()은 input()보다 빠르다고 한다. 확인해보자...!
• set에 단어를 저장하여 중복된 단어를 제거한다. 이후, list로 변환하여 순서를 유지한다. set은 순서가 없기 때문에 정렬을 위해 list로 변환해야 한다.
• 먼저, sort()를 사용하여 사전 순으로 정렬한다. 사전 순 정렬을 먼저 수행하면, 이후 길이 순 정렬 시 사전 순 정렬이 유지된다. sort(key=len)를 사용하여 길이 순으로 정렬한다. N개를 정렬하는 시간복잡도 O(NlogN)이다. N은 최대 20,000이기 때문에 연산이 약 80,000개로 2초의 시간제한에 무난히 들어오게 된다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차

• "출력 형식이 잘못되었습니다."라는 응답을 받았다. 단어 사이에 한 줄씩 더 띄어져 있다. 출력 형식이 잘못된 이유는 입력받은 단어에 개행 문자가 포함되어 있기 때문이다. 입력을 받을 때 개행 문자를 제거해야 출력 형식이 올바르게 나올 것이다.
• strip()을 사용해 개행 문자를 제거하기로 했다. strip() 함수는 문자열의 앞뒤 공백과 개행 문자를 제거해준다. 단어를 입력받을 때마다 sys.stdin.readline().strip()을 사용하여 개행 문자를 제거해 보았다. 이렇게 하면 입력받은 단어의 끝에 개행 문자가 남지 않게 된다.

import sys

number = int(sys.stdin.readline())
wordsset = set()


for i in range(number):
    word = sys.stdin.readline()
    wordsset.add(word)

wordslist = list(wordsset)
wordslist.sort()
wordslist.sort(key=len)
    
for result in wordslist:
    print(result)

---

2회차

• 시간 132ms
• strip()을 사용하여 단어의 양쪽 공백을 제거하였다. 올바르게 동작했지만, 입력 방식을 다르게 해보면 성능 차이가 있을지 궁금해졌다. input()과 sys.stdin.readline()의 시간을 비교해보고 싶었다.

import sys

number = int(sys.stdin.readline())
wordsset = set()

for i in range(number):
    word = sys.stdin.readline().strip()
    wordsset.add(word)

wordslist = list(wordsset)
wordslist.sort()  # 사전 순 정렬
wordslist.sort(key=len)  # 길이 순 정렬

for result in wordslist:
    print(result)

---

3회차

• 시간 188ms
• input()보다 sys.stdin.readline()이 더 효율적이라는 것을 확인했다. sys.stdin.readline()은 input()보다 빠르게 처리할 수 있다. 최종적으로 sys.stdin.readline()을 사용하기로 결정했다.

number = int(input())
wordsset = set()

for i in range(number):
    word = input().strip()
    wordsset.add(word)

wordslist = list(wordsset)
wordslist.sort()  # 사전 순 정렬
wordslist.sort(key=len)  # 길이 순 정렬

for result in wordslist:
    print(result)

 

 

➡️ 정답 코드

import sys

number = int(sys.stdin.readline())
wordsset = set()

for i in range(number):
    word = sys.stdin.readline().strip()
    wordsset.add(word)

wordslist = list(wordsset)
wordslist.sort()  # 사전 순 정렬
wordslist.sort(key=len)  # 길이 순 정렬

for result in wordslist:
    print(result)