알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.
접근 방법: sort() 이용
- 문자열이 있는 리스트에
sort()를 사용하면 사전 순서로 리스트를 정렬해준다. 단, 문제에서 사전 순서보다 문자열의 길이를 우선으로 정렬하라고 하였으므로key값을 이용해 정렬하는 우선순위를 정해주면 될 것 같다.
코드
import sys
words = set()
for _ in range(int(sys.stdin.readline())):
words.add(sys.stdin.readline().strip())
print(*sorted(words, key=lambda x: (len(x), x)), sep='\n')- 중복된 단어는 삭제하여야 하므로
set()에 단어를 입력받았다. sort()함수에key를 넣어주면 그 방식대로 정렬을 해주는데, 여기에 람다식으로 튜플을 넣어주면 요소 순서대로 정렬을 시도해준다. 가장 먼저 단어의 길이에 따라 정렬해야 하므로len(x)을 써주었고, 길이가 같은 문자열에 대해서는x를 써주어 디폴트값인 사전 순서로 정렬되게 작성했다.
결과
접근 방법: Merge sort, Quick sort 구현
- 파이썬 내부 함수를 사용하지 않고 병합 정렬과 퀵 정렬을 직접 구현하여 사용했다.
코드
class WordSort:
# 문제에서 요구하는 정렬 조건을 담은 내부 메소드
def _compare(self, val1, val2):
i, j = len(val1), len(val2)
if i == j:
for n, m in zip(val1, val2):
if ord(n) != ord(m):
return ord(n) - ord(m)
return i - j
# 두 리스트를 병합하는 메소드
def merge(self, arr1, arr2):
ret = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if self._compare(arr1[i], arr2[j]) < 0:
ret.append(arr1[i])
i += 1
else:
ret.append(arr2[j])
j += 1
if i < len(arr1):
ret.extend(arr1[i:])
if j < len(arr2):
ret.extend(arr2[j:])
return ret
# merge 함수를 이용하여 병합 정렬을 하는 메소드
def merge_sort(self, lst):
if len(lst) <= 1:
return lst
return self.merge(self.merge_sort(lst[:len(lst) // 2]), self.merge_sort(lst[len(lst) // 2:]))
# 퀵 정렬 메소드
def quick_sort(self, lst, start, end):
def partition(part, ps, pe):
i = ps - 1
for j in range(ps, pe):
if self._compare(part[j], part[pe]) < 0:
i += 1
part[i], part[j] = part[j], part[i]
part[i + 1], part[pe] = part[pe], part[i + 1]
return i + 1
if start >= end:
return None
p = partition(lst, start, end)
self.quick_sort(lst, start, p - 1)
self.quick_sort(lst, p + 1, end)
return lst결과
- https://ohmyluck.com/ko/random-word/
- 위 사이트에서 랜덤 영어단어를 중복 포함 10000개 정도 뽑아 돌려본 결과 병합정렬과 퀵정렬은 비슷한 시간을 보였고, 파이썬에서 기본적으로 제공하는 팀소트가 압도적으로 빠른 모습을 볼 수 있었다. 물론 직접 구현한 두 정렬의 경우 최적화를 고려하지 않고 작성한 코드이므로 실행결과가 직접적인 성능차로 나타난다고 보긴 힘들 것이다.
