99클럽 코테 스터디 7일차 TIL

오늘의 학습 키워드

해시

과제

윤수와 정환은 「전주 듣고 노래 맞히기」라는 게임을 할 예정이다. 「전주 듣고 노래 맞히기」는 주어진 노래의 전주를 듣고 먼저 제목을 맞히는 사람이 점수를 얻어 최종적으로 점수가 더 많은 사람이 이기는 게임이다. 절대 음감을 가진 윤수는 노래의 첫 네 음만 듣고도 어떤 노래든 바로 맞힐 수 있다. 따라서, 정환은 윤수를 이기기 위해 첫 세 음만으로 노래를 맞히게 해주는 프로그램을 만들려고 한다. 우선 정환이 알고 있는 노래 제목, 음이름 등을 데이터로 만든 뒤 프로그램을 구현하기 시작했다. 예를 들어, 다음은 TwinkleStar(반짝반짝 작은 별)의 악보 중 일부이다.

https://upload.acmicpc.net/42349570-4719-4239-968b-f1704537e702/-/preview/

위 악보를 박자와 관계없이 음이름으로 표현하면 CCGGAAG가 된다.

윤수를 이기기 위해서는 이 프로그램이 첫 세 음인 CCG만으로 노래 제목인 TwinkleStar를 출력할 수 있어야 한다. 또한, 세상의 모든 노래를 아는 윤수와 다르게 정환은 음을 아는 노래가 N$N$개뿐이다. 그래서 프로그램에 N$N$개의 노래의 정보를 저장해 놓을 것이다. 만약 저장된 노래 중 입력한 첫 세 음으로 시작하는 노래가 여러 개 있어 무슨 노래인지 정확히 알 수 없는 경우 ?를 출력하고, 입력한 첫 세 음에 맞는 저장된 노래가 없을 경우 !를 출력한다.

정환을 도와서 첫 세 음만으로 본인이 음을 아는 노래를 맞히는 프로그램을 완성하자. 이 프로그램은 대문자와 소문자를 구분한다.

입력

첫 번째 줄에 정환이 음을 아는 노래의 개수 N$N$, 정환이 맞히기를 시도할 노래의 개수 M$M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 N$N$개의 줄에 걸쳐 노래 제목의 길이 T$T$, 영어 대소문자로 이루어진 문자열 노래 제목 S$S$, 해당 노래에서 처음 등장하는 일곱 개의 음이름 a1,a2,a3,a4,a5,a6,a7$a_1, a_2, a_3, a_4, a_5, a_6, a_7$이 공백으로 구분되어 주어진다.

N+2$N+2$번째 줄부터 M$M$개의 줄에 걸쳐 정환이 맞히기를 시도할 노래의 첫 세 음의 음이름 b1,b2,b3$b_1, b_2, b_3$가 공백으로 구분되어 주어진다.

주어지는 음이름은 각각 C, D, E, F, G, A, B 중 하나이다. 같은 제목이 두 번 이상 주어지지 않는다.

출력

정환이 맞히기를 시도할 각 노래에 대하여 프로그램에 저장된 노래와 첫 세 음이 동일한 노래가 하나만 있다면 해당 노래의 제목을, 두 개 이상이면 ?을, 없다면 !을 한 줄에 하나씩 출력한다.

풀이 과정

1. 노래 개수 N과 맞힐 노래 개수 M 입력 받는데
2. N개의 노래 정보 입력받는다
3. 테스트할 세 음 입력받고, 첫 세 음이 일치하는지 확인하고, 저장된 노래들과 비교한다.
4. 바탕으로 결과를 출력한다.

제출 코드 (python)

N, M = map(int, input().split())
songs = {}

for _ in range(N):
    info = input().split()
    title = info[1]  
    first_three = info[2:5] 
    songs[title] = first_three

for _ in range(M):
    test_notes = input().split() 
    count = 0  
    matched_title = ""  

    for title, notes in songs.items():
        if test_notes == notes:
            count += 1
            matched_title = title
   
    if count > 1:
        print("?")
    elif count == 1:
        print(matched_title)
    else:
        print("!")

다른 언어로 문제 풀기

GO 언어

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    
    var N, M int
    scanner.Scan()
    fmt.Sscanf(scanner.Text(), "%d %d", &N, &M)
    songs := make(map[string][]string)
    
    for i := 0; i < N; i++ {
        scanner.Scan()
        info := strings.Fields(scanner.Text())
        title := info[1]
        firstThree := info[2:5]
        songs[title] = firstThree
    }
    
    for i := 0; i < M; i++ {
        scanner.Scan()
        testNotes := strings.Fields(scanner.Text())
        
        count := 0
        matchedTitle := ""
        
        for title, notes := range songs {
            match := true
            for j := 0; j < 3; j++ {
                if testNotes[j] != notes[j] {
                    match = false
                    break
                }
            }
            if match {
                count++
                matchedTitle = title
            }
        }
        
        if count > 1 {
            fmt.Println("?")
        } else if count == 1 {
            fmt.Println(matchedTitle)
        } else {
            fmt.Println("!")
        }
    }
}

C++

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    map<string, vector<string>> songs;
    
    for(int i = 0; i < N; i++) {
        string index, title;
        vector<string> notes(3);
        
        cin >> index >> title;
        for(int j = 0; j < 3; j++) {
            cin >> notes[j];
        }
        
        songs[title] = notes;
    }
    
    for(int i = 0; i < M; i++) {
        vector<string> testNotes(3);
        for(int j = 0; j < 3; j++) {
            cin >> testNotes[j];
        }
        
        int count = 0;
        string matchedTitle = "";
        
        for(const auto& [title, notes] : songs) {
            bool match = true;
            for(int j = 0; j < 3; j++) {
                if(testNotes[j] != notes[j]) {
                    match = false;
                    break;
                }
            }
            if(match) {
                count++;
                matchedTitle = title;
            }
        }
        
        if(count > 1) {
            cout << "?" << "\\n";
        } else if(count == 1) {
            cout << matchedTitle << "\\n";
        } else {
            cout << "!" << "\\n";
        }
    }
    
    return 0;
}

오늘의 회고

• 문제가 꽤 길어서 전과 다르게 시간이 걸렸다

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