[99클럽 4기 코테 스터디 TIL 7일차] 전주 듣고 노래 맞히기 (feat. 해시맵)

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

• 어제는 백준에서 한 줄에 공백으로 구분되어 입력받은 값을 String.split()를 이용해 배열에 저장했다.

String[] morseCode = br.readLine().split(" ");

• 오늘은 공백으로 구분된 입력값을 StringTokenizer.nextToken()를 이용해 저장해 사용해보겠다.

StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());

 

 

1) 내가 구현한 코드

import java.util.*;
import java.io.*;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        HashMap<String,String> map = new HashMap<>(); //"노래제목" : "음이름"

        int N = Integer.parseInt(st.nextToken()); //음을 아는 노래의 개수
        int M = Integer.parseInt(st.nextToken()); //정환이 맞히기를 시도할 노래의 개수

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int T = Integer.parseInt(st.nextToken()); //노래제목의 길이 - 필요없음
            String S = st.nextToken();//영어 대소문자로 이루어진 문자열 노래 제목
            String code = "";
            for(int j=0; j<3; j++){
                code += st.nextToken();
            }
            map.put(S,code);
        }
//        System.out.println(map);

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            String correctCode = "";
            for(int j=0; j<3; j++){
                correctCode += st.nextToken();
            }

            int cnt=0; //첫 세 코드가 같을 경우 카운트
            String name =""; //제목 출력
            for(Map.Entry<String,String> entry:map.entrySet()){
//                entry.getKey();
//                entry.getValue();
                if(correctCode.equals(entry.getValue())) {
                    name = entry.getKey();
                    cnt++;
                }
            }

            if(cnt >= 2){
                bw.write("?\n");
            }else if(cnt == 1){
                bw.write(name+"\n");
            }else{
                bw.write("!\n");
            }
        }
        bw.flush();

        br.close();
        bw.close();
    }

}

 

 

 

2) 오늘의 학습 키워드

• 해시맵을 사용하여 빠르게 데이터 검색하기
• 조건을 통해 여러 결과 중 일치하는 항목을 필터링하는 방법
• 입력 및 문자열 처리

 

 

 

3) 문제 이해

• 이 문제는 전주 듣고 노래 맞히기라는 게임의 룰을 코드로 구현하는 것이다.
• 주어진 첫 세 음을 기반으로 노래 제목을 추론하고,
• 동일한 패턴을 가진 노래가 여러 개일 경우 ?, 없을 경우 !, 정확히 하나의 노래만 있으면 해당 제목을 출력하도록 한다.

 

 

4) 문제 해결 과정

1. 접근 방식

• 입력 데이터 저장: 주어진 노래 정보를 저장하기 위해 HashMap을 사용하여 노래 제목을 값으로, 첫 세 음을 키로 저장한다.
• 패턴 검색: 정환이 맞히기를 시도할 각 첫 세 음에 대해 해시맵을 조회한다.
  • 조회된 노래가 하나뿐이라면 제목을 반환한다.
  • 동일 패턴을 가진 노래가 여러 개일 경우 ?을 출력한다.
  • 일치하는 노래가 없을 경우 !를 출력한다.

2. 문제 해결 과정

• 데이터 저장
  • 방법1 
    • "노래제목" : "첫 세음" 
    • 각 노래제목과 노래의 첫 세음을 key: value로 해시맵에 저장한다.
  • 방법2
    • "첫 세음" : ["노래제목1", "노래제목2", "노래제목3" ..]
    • 각 노래의 첫 세 음을 키로 하여 해시맵에 저장한다.
    • 이미 해당 키가 존재한다면 목록에 추가하여, 특정 패턴으로 시작하는 노래가 여러 개일 경우를 대비한다.
• 출력 조건 구현: 검색 시
  • 일치하는 노래가 하나일 때: 제목을 출력
  • 일치하는 노래가 여러 개일 때: ? 출력
  • 일치하는 노래가 없을 때: ! 출력

3. 추가 구현 코드

import java.io.*;
import java.util.*;

public class SongGuessingGame {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 첫 번째 줄 입력 처리
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  // 정환이 아는 노래 수
        int M = Integer.parseInt(st.nextToken());  // 맞히기를 시도할 노래 수

        // 노래 정보를 저장할 해시맵
        HashMap<String, List<String>> songMap = new HashMap<>();

        // N개의 노래 정보 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int T = Integer.parseInt(st.nextToken());  // 노래 제목의 길이 (사용하지 않음)
            String title = st.nextToken();  // 노래 제목

            // 첫 7개의 음을 배열에 저장
            String[] notes = new String[7];
            for (int j = 0; j < 7; j++) {
                notes[j] = st.nextToken();
            }

            // 첫 세 음을 키로 하여 저장
            String firstThreeNotes = notes[0] + notes[1] + notes[2];
            songMap.putIfAbsent(firstThreeNotes, new ArrayList<>());
            songMap.get(firstThreeNotes).add(title);
        }

        // M개의 노래 맞히기 시도
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            String firstNote = st.nextToken();
            String secondNote = st.nextToken();
            String thirdNote = st.nextToken();

            String guessPattern = firstNote + secondNote + thirdNote;
            
            // 패턴에 맞는 노래 찾기
            if (songMap.containsKey(guessPattern)) {
                List<String> matchedSongs = songMap.get(guessPattern);
                if (matchedSongs.size() == 1) {
                    bw.write(matchedSongs.get(0) + "\n");
                } else {
                    bw.write("?\n");
                }
            } else {
                bw.write("!\n");
            }
        }

        // 버퍼에 남아있는 모든 출력 내용을 실제 출력
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

5) 새로운 배움

• HashMap과 List 활용
  • 여러 값이 동일한 키를 가질 수 있는 경우, HashMap의 값으로 List를 사용해 효율적으로 저장하고 조회할 수 있었다.
• 패턴 매칭 조건 구현
  • 다양한 조건을 활용해 패턴 매칭 문제를 해결하는 법을 익혔다.
• 입출력 관리
  • 노래의 입력과 첫 세 음의 패턴이 주어졌을 때 이를 정확히 읽고 필요한 부분만 저장하는 효율적인 관리 방법을 익혔다.

 

 

6) 내일의 학습 목표

• 문자열과 해시맵을 활용한 문제를 더 연습하여 숙달하기
• 다양한 패턴의 조건을 확인하고 대응하는 조건문 구성 연습
• 해시맵의 사용법을 더 심화하여, 키와 값의 관계를 최적화할 수 있는 방법 학습하기

 

7) 추가 문제

미들러 - 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

챌린저 - 노드 사이의 거리

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