문제: https://www.acmicpc.net/problem/20920
딕셔너리 자료형과 정렬 그리고 문자열이 관련된 문제이다.
특히 딕셔너리의 정렬을 잘 숙지 할 수 있는 문제이다.
문제 해석
단어들을 가지고 단어장을 만들 것이다. 길이 M 미만 단어들은 단어장에 추가하지 않고 다음 기준들로 단어들을 추가 및 정렬한다.
- 자주 나오는 단어일수록 앞에 배치한다. (내림차순)
- 해당 단어의 길이가 길수록 앞에 배치한다. (내림차순)
- 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다. (오름차순)
1번 기준으로 정렬하다가 동일 값이 나올 경우 2번 기준으로, 또 동일 값이 나오면 3번으로 넘어가는 방식으로 구현한다.
해결 방법
- 길이 M 이상의 단어들을 딕셔너리 자료형으로 저장한다.
- 딕셔너리의 키는 단어, 값은 [개수, 길이, 단어] 로 지정한다.
- sorted함수의 key 인자 값으로 정렬의 기준과 우선순위를 정한다.
코드 해석
[i] 딕셔너리 생성
단어를 입력받고 단어 길이가 M 미만이면 단어장에 추가하지 않는다.
M을 넘는다면 딕셔너리에 해당 단어 존재 여부를 확인하고 없다면 딕셔너리 키는 단어로, 딕셔너리 값은 [1(단어 개수), 단어 길이, 단어] 으로 설정한다.
해당 단어가 딕셔너리에 존재한다면 해당 딕셔너리의 값에서 개수 하나를 증가시킨다.
딕셔너리 값 리스트의 0번 인덱스는 단어의 개수, 1번 인덱스는 단어의 길이, 2번 인덱스는 단어 값을 의미한다.
[ii] 정렬
이제 생성한 딕셔너리를 정렬할 것이다. 파이썬의 sort 및 sorted 함수는 key 인자 값으로 정렬에 있어서 우선 순위 기준을 설정 할 수 있다.
sort(key= lambda x: (기준1, 기준2, 기준3))해당 문제에서는 딕셔너리 값으로 준 [개수, 길이, 단어] 이렇게 3가지를 가지고 기준을 설정하고 정렬 할 것이다.
이렇게 여러개를 정렬 기준으로 넣어주면 앞에 있는 기준부터 차례대로 정렬하고 동일 값이 나오면 그 다음 기준으로 정렬을 실행한다.
여기서 중요한 점이 있다.
정렬 함수는 추가 인자 값으로 reverse = True 를 줌으로써 내림차순 정렬을 실행할 수 있다.
sort(key= lambda x: (기준이 될 값), reverse = True)그러나 다양한 정렬 기준이 있을 때reverse = True 를 쓰게 되면 모든 기준들이 일괄적으로 내림차순 정렬이 된다.
이는 이번 문제와 같이 정렬 기준들의 오름차순 내림차순 설정을 각각 다르게 해주어야 한다면 문제가 생긴다.
이 문제는 기준으로 주는 값 앞에 마이너스(-)를 붙여주면서 해결 가능하다. 아래와 같이 마이너스를 붙여준 해당 그 기준만 내림차순으로 정렬 시킬 수 있다.
sort(key= lambda x: (-기준1, 기준2, 기준3))다만 이는 숫자형만 적용 되는 것이고 문자형은 적용이 되지 않는다. 그래서 숫자형 기준을 잘 조작하여서 문제에서 제시하는 기준을 잘 맞출 수 있도록 해야한다.
해당 문제에서는 개수, 길이는 내림차순으로 단어순서는 오름차순으로 설정하라고 했으므로 개수와 길이 기준 앞에 마이너스(-)를 붙였다. 아래 코드에서 확인 가능하다.
코드
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
d = {}
for _ in range(n):
name = input().strip()
# 단어길이가 M보다 작으면 패스
if len(name) < m:
continue
# d.get()은 해당 값이 존재하면 값을 반환 없으면 None을 반환
if d.get(name):
# 단어가 존재하면 개수 하나 증가
d[name][0] += 1
else:
# 존재하지 않으면 [개수, 길이, 단어] 추가
d[name] = [1, len(name), name]
# 개수, 길이는 내림차순으로 단어는 사전순(오름차순)으로 정렬
ans = sorted(d.items(), key= lambda x: (-x[1][0], -x[1][1], x[1][2]))
for a in ans:
print(a[0])정렬 문제에서 우선 순위 기준 설정 공부에 도움을 줄 수 있는 문제이다.
