문제:
화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.
- 자주 나오는 단어일수록 앞에 배치한다.
- 해당 단어의 길이가 길수록 앞에 배치한다.
- 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.
입력:
첫째 줄에는 영어 지문에 나오는 단어의 개수 과 외울 단어의 길이 기준이 되는 이 공백으로 구분되어 주어진다. (1≤ N ≤100,000, 1≤ M ≤10)
둘째 줄부터 번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 을 넘지 않는다.
단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.
출력:
화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.
풀이방법:
defaultdict을 사용해서 나오는 횟수를 카운팅하며 (key, value) 값을 조건에 맞게 정렬하고 출력하도록 한다.
시간 제한이 걸려 있는 문제이므로 일반 input 대신 sys.stdin.readline을 사용해야 하며, rstrip()으로 개행문자를 제거해 주도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
count_dict = defaultdict(int)
for _ in range(N):
word = input().rstrip()
if len(word) >= M:
count_dict[word]+=1
counts = sorted(count_dict.items(), key=lambda x: (-x[1], -len(x[0]), x[0]))
for c in counts:
print(c[0])
|
cs |
문제링크:
https://www.acmicpc.net/problem/20920
20920번: 영단어 암기는 괴로워
첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [Programmers] Lv 2. 무인도 여행 (0) | 2023.07.21 |
|---|---|
| [BOJ] 19941. 햄버거 분배 (0) | 2023.07.20 |
| [Programmers] Lv 2. 연속된 부분 수열의 합 (0) | 2023.07.18 |
| [BOJ] 21921. 블로그 (0) | 2023.07.17 |
| [Programmers] Lv 2. 롤케이크 자르기 (0) | 2023.07.14 |