전주 듣고 노래 맞히기_백준31562

 

<문제>

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

 

<풀이>

import sys

input = sys.stdin.read().splitlines()
N, M = map(int, input.pop(0).split())

known_dict = {}

for i in range(N):
    notes = input[i].split()

    T = int(notes.pop(0))
    name = notes.pop(0)

    first_notes = ''.join(notes)[0:3]

    if first_notes not in known_dict:
        known_dict[first_notes] = [name]
    else:
        known_dict[first_notes].append(name)

for j in range(N, N + M):
    test_notes = input[j].replace(' ', '')
    match = len(known_dict[test_notes]) if test_notes in known_dict else 0

    if match > 1:
        print('?')
    elif match == 1:
        print(known_dict[test_notes][0])
    else:
        print('!')

 

- 문자열 다루기 + 해시테이블 

- 3음을 문자열으로 만들어서 key로

- 노래 제목을 key의 value로

- 그런데 key가 겹칠 수 있으므로 value가 2개 이상이 올 수 있음 -> linked list, 다음에 오는 노드를 뒤로 붙이기

- 문제에서는 단순히 value의 갯수가 1개 이상인지를 알면 되므로 len만 필요

- 테스트 3음을 key로 조회해서 각각 print