[Python][백준] 20920. 영단어 암기는 괴로워

링크🔗

https://www.acmicpc.net/problem/20920

---

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) # 단어 개수, 단어 길이

word_lst = {}

for n in range(N):
    word = input().rstrip()
    if len(word) >= M :
        if word in word_lst:
            word_lst[word] += 1
        else: 
            word_lst[word] = 1
    

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

for w_lst in word_lst:
    print(w_lst[0])

 

1. input = sys.stdin.readline으로 설정해주고,  단어를 입력 받을 때, rstrip() 함수로 받아준다.

✨ rstrip 은 문자열의 오른쪽 끝에서 공백이나 특정 문자를 제거해주는 매서드
rstrip() 같은 경우 공백을 제거 / rstrip("!") 같은 경우 ! 를 제거

 

2. 딕셔너리(해쉬)로 받아주고, 단어 빈도수 넣어준다.

 

3. sorted 매서드의 다중 조건을 사용해서 word_lst.item()의 순서를 조건에 맞게 정렬한다.

 

(1.빈도수 / 2. 단어 길이 / 3. 알파벳 사전 순)

🚨 word_lst.item()이 아닌 word_lst (딕셔너리)형태로 sorted 정렬을 하면 에러가 발생한다.
sorted 정렬을 하려면 리스트 형태가 되어야 한다,

 

📕 내 풀이 (시간 초과)

N, M = map(int,input().split(" "))

# 빈토수, 길이 
def frq_len():
    for s_l in set_lst:
        frq_cnt.append(lst.count(s_l)*200)
        len_cnt.append(len(s_l)*10)
    return 0

# 알파벳 순서
def alp():
    num = len(total_rank)
    for i in range(num-1):
        for j in range(i+1,num):
            if total_rank[i] == total_rank[j]:
                cnt = 0
                while True : 
                    if ord(set_lst[i][cnt]) > ord(set_lst[j][cnt]):
                       total_rank[j] += 1
                       break
                    elif ord(set_lst[i][cnt]) < ord(set_lst[j][cnt]): 
                        total_rank[i] += 1
                        break
                    cnt += 1
    return 0

lst = []
# M 이하의 수 제외
for n in range(N):
    tmp = input()
    if len(tmp) >= M :
        lst.append(tmp)

set_lst = list(set(lst))

frq_cnt = []  # 단어 빈도수 확인
len_cnt = []  # 해당 단어 길이 
total_rank = [0] * len(set_lst) 

frq_len()

for i in range(len(set_lst)):
    total_rank[i] = frq_cnt[i] + len_cnt[i]

alp()

order_rank = sorted(total_rank,reverse=True)

for i in range(len(total_rank)):
    print(set_lst[total_rank.index(order_rank[i])])

 

1. sorted의 조건을 걸고 정렬 할 생각을 하지 않은, 아주 무식한 정렬 방식이다...

 

2. 간단한 로직을 말해보자면,  M 이하 길이는 리스트에 저장 하지 않는다.

 

3. frq_len (빈도수와 길이를 계산하는 함수)를 통해 계산을 하는데, 우선 순위 점수를 부여한다. 

이때 점수 부여는 빈도수 * 200 점  / 길이 * 10점 이런식으로 했는데, 이유는 길이가 아무리 많아도 빈도수 우선 순위를 못 따라가게 만들기 위해서이다. 

 

4. total_rank는 빈도수 점수와 단어 길이 점수를 더한 리스트이고, alp 함수를 호출하여서 만일 total_rank에 같은 값이 있다면 알파벳 순서가 낮은 단어에 + 1 점을 주어 우선권을 높힌다.

 

5. 최종적으로 구해진 order_rank / total_rank / set_lst를 잘 인덱싱 해서 출력하면 된다. 

 

🚨 주어진 예시에 답은 맞게 나오는데, 최종 결과는 시간 초과로 뜬다 ㅠㅠ  

복잡한 과정이지만, 나름 괜찮은 아이디어라 생각했는데,  

역시 복잡할 때는 다시 다른 방법을 생각하는게 좋은 것 같다...

 

 

📌  문제 코멘트

정렬의 다중 조건을 lambda를 통해 넣을 수 있으면 그다지 구현이 어려운 문제는 아니다. 
다만,  주의 해야 할 것 들이 있다.

1. input = sys.stdin.readline은 필수  
(이렇게 설정하면 기존의 input 함수가 불필요한 개행 문자 자동 제거하는 추가 작업을 줄여줌,
여기 문제에서는 이거 설정 안하면 시간 초가 발생함 )

2. rstrip()
효율적인 버퍼 사용을 위해 input = sys.stdin.readline 로 설정고, 한 번에 한줄을 읽어오기 때문에, 공백을 rstrip으로 제거해야 한다. 

3.  sorted는 리스트에만 가능 
word_lst, 즉 딕셔너리로 정렬하려 하면 안되고, word_lst.items() 형태로 바꿔서 정렬해야 한다. 

 

---

📚문제

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

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

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

입력

첫째 줄에는 영어 지문에 나오는 단어의 개수 𝑁$N$과 외울 단어의 길이 기준이 되는 𝑀$M$이 공백으로 구분되어 주어진다. (1≤𝑁≤100000$1 \leq N \leq 100\,000$, 1≤𝑀≤10$1 \leq M \leq 10$)

둘째 줄부터 𝑁+1$N+1$번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10$10$을 넘지 않는다.

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

출력

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

예제 입력 1 복사

7 4
apple
ant
sand
apple
append
sand
sand

예제 출력 1 복사

sand
apple
append

예제 입력 2 복사

12 5
appearance
append
attendance
swim
swift
swift
swift
mouse
wallet
mouse
ice
age

예제 출력 2 복사

swift
mouse
appearance
attendance
append
wallet