문제출처
https://www.acmicpc.net/problem/1181
걸린시간: 16분 47초
문제분석
문자열이 여러개 주어졌을 때 중복되는 문자열은 제거하고 길이가 짧은 순부터 단어가 정렬하되 동일한 길이의 경우, 사전 순으로 정렬해야하는 문제다.
최대 2초 내에 최대 20000개의 데이터를 처리해야하므로 알고리즘의 시간복잡도는 O(N^2)을 넘어서는 안된다.
문제접근
내 접근
from sys import stdin
input = stdin.readline
n = int(input())
my_words = [input().strip() for x in range(n)]
# 사전순으로 정렬하기
my_words.sort() # 문자열인 경우 사전순으로 정렬하는 듯 하다.
# 길이순으로 정렬하기
my_words.sort(key = lambda x:len(x)) # key 값을 활용하여 정렬기준을 설정할 수 있다.
# 중복 제거하기
my_words = list(dict.fromkeys(my_words))길이가 짧은 순부터 단어를 정렬하되, 동일한 길이의 경우 사전 순으로 정렬해야하는 조건을 충족하기 위해 리스트로 받은 단어들을 사전 순으로 정렬을 한 후 길이 순으로 정렬했다.
길이를 기준으로 먼저 정렬을 하게 되면 단어들은 알파벳 순이 우선순위 기준으로 정렬하게 된다.
문자열을 담은 리스트에 sort함수를 사용하면 사전순으로 정렬하게 된다.
my_words.sort()
다른 기준으로 리스트를 정렬하려면 람다함수를 활용할 수 있다. 문제에서는 문자열의 길이를 기준으로 한번 더 정렬을 하였다.
my_words.sort(key = lambda x:len(x))sort함수 내부에 매개변수로 `key = lamdba x:len(x)`를 사용하면 key를 기준으로 문자열이 정렬하게 된다.
리스트에 있는 중복 문자열을 제거하기 위해 set을 이용하는 방법과 dict을 이용하는 방법이 있었다. 전자의 경우, 리스트에 있는 원소들의 순서를 보장할 수 없었기 때문에 dict을 사용했다.
my_words = list(dict.fromkeys(my_words))코드개선
from sys import stdin
input = stdin.readline
# 데이터를 받을 때 한번만 쓰는 데이터는 별도의 변수를 둘 필요가 없음 + 사전에 중복 제거
my_words = set()
for i in range(int(input())):
my_words.add(input().strip())
# 정렬 로직을 한번에 처리할 수 있음: 1. 사전순 정렬 2. 크기 순 정렬
for i in sorted(sorted(list(my_words)), key=lambda x:len(x)):
print(i)내 코드의 경우, 정렬을 한 후에 순서를 유지하기 위해 어쩔 수 없이 dict을 활용하여 중복을 제거했다. 하지만 데이터를 처음부터 받을 때 리스트 대신에 set으로 받았다면 정렬 순서를 해치는 것을 고려하지 않아도 됐다.
배운점
- 문자열 리스트에 sort함수 사용시 사전순으로 정렬된다.
- sort, sorted 함수에 key를 통해 람다식을 활용하여 다른 기준으로 요소들을 정렬할 수 있다.