article thumbnail image
Published 2024. 11. 3. 18:35
728x90

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

 

오늘은 백준 에서 31562 전주 듣고 노래 맞히기 에 대해서 진행해보도록하겠습니다.

 


문제 :

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

 

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

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

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


입력 :

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

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

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

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

 

출력 : 

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

 

예제 :

4 4
11 TwinkleStar C C G G A A G
8 Marigold E D E F E E D
23 DoYouWannaBuildASnowMan C C C G C E D
12 Cprogramming C C C C C C C
E D E
C G G
C C C
C C G

 

JAVA  

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(NM[0]); // 음을 아는 노래의 개수 N
        int M = Integer.parseInt(NM[1]); // 맞출 노래의 개수 M

        String[][] musicInfo = new String[N][]; // [제목 길이, 제목, 음이름]이 담긴 이차원 배열 선언

        for(int i = 0; i < N; i++) {
            musicInfo[i] = br.readLine().split(" "); // 음악 정보 초기화
        }

        for(int j = 0; j < M; j++) {
            int cnt = 0;
            String code = br.readLine().replaceAll(" ", ""); 
            ArrayList<String> list = new ArrayList<>(); 
            for(int i = 0; i < N; i++) {
                // code와 가장 맨앞부터 3개의 음이름 같으면 list에 저장
                if((musicInfo[i][2] + musicInfo[i][3] + musicInfo[i][4]).equals(code)) {
                    list.add(musicInfo[i][1]);
                }
            }

            int listSize = list.size();

            if(listSize == 1) { // size 1이면 제목 출력
                System.out.println(list.get(0));
            }
            else if(listSize > 1) { // size 1보다 크면 ? 출력
                System.out.println("?");
            }
            else { // size 0이면 ! 출력
                System.out.println("!");
            }
        }
    }

 

JAVA 2

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());

        Map<String, String> map = new HashMap<>();
        while (n-- > 0) {
            String[] arr = br.readLine().split(" ", 3);
            String key = arr[2].substring(0, 5);

            map.put(key, map.containsKey(key) ? "?\n" : arr[1] + "\n");
        }

        while (m-- > 0) sb.append(map.getOrDefault(br.readLine(), "!\n"));

        bw.write(sb.toString());
        bw.flush();
    }

 

둘의 장단점 : 

첫 번째 코드 (JAVA)

장점:
명확한 흐름: 입력을 받고 처리하는 과정이 명확하게 나누어져 있어 이해하기 쉽습니다.
직관적인 비교: 코드가 음악 정보를 직접 비교하여 일치 여부를 판단하므로, 쿼리의 결과를 이해하기 쉽게 출력합니다.

단점:
비효율성: 모든 쿼리에 대해 음악 정보를 매번 순회하여 비교하므로, 시간이 오래 걸릴 수 있습니다. 쿼리 수가 많아지면 성능이 저하될 수 있습니다.
중복 출력 처리: 중복된 제목이 있을 때, 명시적으로 "?"를 출력하는 로직이 필요하여 코드가 다소 복잡해질 수 있습니다.


두 번째 코드 (JAVA2)

장점:
해시맵 사용: 음악 코드와 제목을 해시맵에 저장하여 O(1) 시간 복잡도로 쿼리를 처리할 수 있습니다. 이로 인해 성능이 크게 향상됩니다.
중복 처리 간편화: 해시맵에 키가 이미 존재할 경우 "?"로 처리하므로, 코드가 간결해지고 중복 제목 처리가 쉽게 이루어집니다.
효율적인 입출력: BufferedWriter와 StringBuilder를 사용하여 입출력을 효율적으로 처리합니다.

단점:
코드 이해의 어려움: 해시맵 사용과 관련된 부분이 초보자에게는 직관적이지 않을 수 있습니다. 코드의 흐름이 첫 번째 코드에 비해 다소 복잡하게 느껴질 수 있습니다.
고정된 키 길이: 코드의 처음 5글자만 사용하므로, 만약 코드가 5글자 이하로는 구분할 수 없는 경우가 생길 수 있습니다.


결론
성능을 중시한다면 두 번째 코드(Main)가 더 좋습니다. 해시맵을 사용하여 쿼리 처리 속도가 빠르고, 중복 처리가 간편하여 전체적인 효율성이 높습니다.
코드의 직관성과 간단함을 중시한다면 첫 번째 코드(bak_31562)가 더 나을 수 있습니다. 읽기 쉬운 구조로 인해 이해하기 쉽습니다.
따라서 사용자의 요구에 따라 선택할 수 있습니다. 성능이 더 중요한 경우에는 두 번째 코드를 추천합니다.
728x90
복사했습니다!