[백준] 31562 - 전주 듣고 노래 맞히기

문제 출처: https://www.acmicpc.net/problem/31562

 

문제

첫 세 음만으로 본인이 음을 아는 노래를 맞히는 프로그램을 완성하자.

 

 

입력

• 첫 번째 줄에 음을 아는 노래의 개수N와 맞히기를 시도할 노래의 개수M이 공백으로 구분되어 주어짐
• 두 번째 줄부터 N줄에 걸쳐 노래 제목의 길이 T와 영어 대소문자로 이루어진 노래 제목 S,
• 해당 노래에 처음 등장하는 일곱개의 음이름이 공백으로 구분되어 주어짐
• N+2번째 줄부터 M개의 줄에 걸쳐 맞히기를 시도할 노래의 첫 세 음이 공백으로 구분되어 주어짐

 

출력

• 입력한 첫 세음으로 시작하는 저장된 노래가 여러 개 있는 경우 : ?
• 입력한 첫 세음에 맞는 저장된 노래가 없는 경우 : !
• 맞는 노래가 한 개인 경우 : 노래 제목

 

풀이 방법

1. 첫 번째 줄은 입력받고 N, M에 각각 저장.
2. 두 번째 줄부터 입력받고 딕셔너리 songs에 첫 세 음을 key로 노래 제목 리스트를 value로 저장.
3. 첫 세 음은 중복될 수 있으므로 이미 존재하는 키일 경우 기존 키의 value로 추가.
4. M번동안 for문 돌리면서 입력받고 입력받은 음이 songs 딕셔너리에 key로 존재하는지 확인.
5. 있으면 value의 길이가 1인 경우 value[0] 출력.
6. value의 길이가 2이상인 경우 ? 출력.
7. 입력받은 음이 songs 딕셔너리에 key로 존재하지 않으면 ! 출력.

 

작성한 코드

import sys

N, M = map(int, sys.stdin.readline().strip().split()) #1

songs = {}

for i in range(N): #2
    song_info = sys.stdin.readline().strip().split()
    S = song_info[1]
    K = song_info[2]+song_info[3]+song_info[4]

    if K not in songs:
        songs[K]=[S]
    else:
        songs[K].append(S) #3 

for i in range(M): #4
    sound = sys.stdin.readline().strip().replace(" ","")
    
    if sound in songs.keys():
        if(len(songs[sound])==1): #5
            print(songs[sound][0])
        elif(len(songs[sound])>=2): #6
            print("?")
    else: #7
        print("!")

 

 

처음에는 노래 제목을 key, 첫 세 음을 value로 하는 딕셔너리를 만들었고, 노래를 맞히는 과정도 이중 for문으로 작성했었다.

N, M이 최대 1,000으로 크지 않았기 때문에 비효율적이었지만 정답 처리는 되었다. 

 

위 코드는 다른 풀이를 참고해서 수정한 코드이다.

처음에 딕셔너리의 key는 중복될 수 없다는 것에 너무 매몰되었던 것 같다.

첫 세 음을 key, 노래 제목 리스트를 value로 갖는 딕셔너리를 만들었다.

이렇게 수정하니 이중 for문을 사용할 필요도 없어져 시간 복잡도 면에서 훨씬 효율적인 코드가 되었다.

실제로 연산 시간이 130ms대에서 30ms대로 확 줄었다.

 

 

참고 자료 : https://hmin99.tistory.com/m/59