[Python] 백준 20920 영단어 암기는 괴로워 - 정렬, 구현, 문자열

백준 홈페이지 문제와 개인적인 풀이를 작성한 글 입니다.

 

백준문제 - 20920 : 영단어 암기는 괴로워

20920번: 영단어 암기는 괴로워

 

---

 

문제

 

이번 영어 시험에서 틀린 문제를 바탕으로 영어 암기를 하려고 한다.

그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려고 하고 있다.

희은이가 만들고자 하는 단ㅇ너장의 단어 순서는 다음과 같은 우선 순위를 차례로 적용하여 만들어진다.

 

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사진 순으로 앞에 있는 단어일수록 앞에 배치한다.

 

M 보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M 이상인 단어들만 외운다고 한다. 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 봅시다.

 

입력

 

첫째 줄에 영어 지문에 나오는 단어의 개수 N 과 외울 단어의 길이 기준이 되는 M 이 공백으로 구분되어 주어진다.

(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 10)

 

둘째 줄부터 N + 1 번째 줄까지 외울 단어를 입력받는다.

이 때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10 을 넘지 않는다.

 

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

 

출력

 

단어장에 들어 있는 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

 

예제 입력 1	예제 출력 1
7 4 apple ant sand apple append sand sand	sand apple append

 

예제 입력 2	예제 출력 2
12 5 appearance append attendace swim swift swift swift mouse wallet mouse ice age	swift mouse appearance attendance append wallet

 

코드 - 실패 (시간 초과)

 

n, m = list(map(int, input().split()))

dict = {}
for i in range(n):
  item = list(input().strip())
  if len(item) < m:
    continue
  if "".join(item) in dict:
    dict["".join(item)] += 1
  else :
    dict["".join(item)] = 1


item_list = sorted(dict.items(), key = lambda x:(-x[1], -len(x[0]), x[0]))


for i in item_list:
  print(i[0])

 

실패 이유 : 시간 초과

 

코딩테스트를 풀면서, 단순한 몇 가지 방법으로 속도를 높일 수 있습니다.

위와 아래의 코드를 비교 해봅시다!

 

입력 폼에 따라, sys 모듈을 사용하면 속도를 줄일 수 있다.

 

사실 입력 폼을 받지 않고, 임의의 입력폼을 이미 받아 놓은 상태에서, 문제를 푸는 경우도 굉장히 많습니다.

(프로그래머스 환경에서 코딩테스트를 할 경우, 입력 폼을 받을 필요가 없습니다.)

그래서 필요없다고 생각하시면 넘기시면 됩니다.

 

하지만, 모든 코딩테스트가 저희에게 맞춰주는 것이 아니라, 제가 시험에 맞추는 것이기 때문에 간단하게 알아두면 좋을 듯 합니다.

 

코드 - 성공

 

import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))

dict = {}
for i in range(n):
  item = list(input().strip())
  if len(item) < m:
    continue
  if "".join(item) in dict:
    dict["".join(item)] += 1
  else :
    dict["".join(item)] = 1


item_list = sorted(dict.items(), key = lambda x:(-x[1], -len(x[0]), x[0]))


for i in item_list:
  print(i[0])

 

알아두면 좋은 것

 

Dictionary ({}) 를 사용하는 경우에는 정렬이랑 연관지어서 나오는 경우가 굉장히 많습니다.

 

lambda x:(-x[1], -len(x[0]), x[0])

 

위의 함수와 같이, 만들 수 있습니다.

 

딕셔너리 의 두번째 값(배열의 1) 로 정렬을 하고, 앞에 ' - ' 문구를 이용하여 reverse = True 와 같이 사용한다.

조금 분석해보겠습니다.

 

# 배열의 두번째 값으로 정렬 내림차순
lambda x: -x[-1]

# 배열의 첫번째 값의 길이로 정렬 내림차순
lambda x: -len(x[0])

# 배열의 첫번째 값으로 정렬 올림차순
lambda x: x[0]