99클럽 코테 스터디 9일차 TIL + 전주 듣고 노래 맞히기

오늘의 학습 키워드 및 문제

#해시 #HashMap #StringToKenizer
백준 브론즈1) 전주 듣고 노래 맞히기

문제풀이

노래에 대한 첫 세 음과 노래 문제의 세 음을 비교하여 출력해야되는 문제라 HashMap을 사용하여 해당되는 value에 대한 key값을 출력하면 되겠다고 생각했다.

1. 음을 아는 노래 개수와 노래 문제 개수 입력받음
2. 음을 아는 노래들을 HashMap에 저장 (key : 노래제목, value : 첫 세 음)
3. 노래 문제 출제 및 문제 맞추기
   3-1. 문제 입력 (replace를 사용하여 공백 제거)
   3-2. HashMap을 반복문하여 문제와 map의 value가 일치하는 것이 있는지 확인
   3-3. 문지열 비교하여 일치하면 cnt++ 및 노래제목 저장
   3-3. cnt의 갯수에 따라 결과 출력

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, String> map = new HashMap<>();
        
        // song[0] : 음을 아는 노래의 개수 , song[1] : 노래 문제 개수
        String[] song = br.readLine().split(" ");
        
        // 음을 아는 노래 저장
        for(int i=0; i<Integer.parseInt(song[0]); i++) {
            // s[0] : 노래 문자열 개수 , s[1] : 노래 제목 , s[2]~ : 노래의 음이름
            String[] s = br.readLine().split(" ");
            map.put(s[1], s[2]+s[3]+s[4]);
        }
        
        // 노래 문제 출제
        for(int i=0; i<Integer.parseInt(song[1]); i++) {
            String s = br.readLine().replace(" ","");
            // 문제 맞추기
            int cnt = 0;
            String name = "";
            for(Map.Entry<String, String> m : map.entrySet()) {
                if(s.equals(m.getValue())) {
                    if (name.equals("")) {
                        name = m.getKey();
                    }
                    cnt++;
                }
            }
            // 결과 출력
            if(cnt == 0) {
                System.out.println("!");
            } else if (cnt == 1) {
                System.out.println(name);
            } else {
                System.out.println("?");
            }
        }
        
        br.close();
    }
}

다른방법

1. String.split() 대신 StringTokenizer 사용

코딩테스트 문제를 풀 때 많은 사람들이 StringTokenizer를 사용한다. 왜일까?

• String.split()
  정규식을 기반으로 동작하여 내부적으로 추가적인 연산을 필요로 한다.
  따라서 다량의 데이터를 처리할 때 느릴 수 있다.
  또한 분리된 문자열을 배열로 반환하기 때문에 입력 문자열의 크기가 크거나 배열의 결과 크기가 클 경우 메모리 사용량이 증가한다.
• StringTokenizer
  정규식 없이 간단히 구분자를 기준으로 문자열을 나누기 때문에 더 빠르게 동작한다.
  또한 입력 문자열을 직접 탐색하며 필요한 순간에만 각 토큰을 반환하므로 메모리 사용량이 더 적다.

2. HashMap 구조 변경 (key를 세 음으로)

key를 세 음으로 지정함으로써 노래 문제를 출제하기 전에 알고 있는 노래 목록에서 첫 세 음이 같은 것이 있는지 확인할 수 있다.

[기존방법] 20684KB 316ms
[다른방법] 18184KB 192ms

// 다른 방법 1,2 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, String> map = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken()); // 알고있는 노래 개수
        int m = Integer.parseInt(st.nextToken()); // 문제 풀제 개수
        
        // 음을 아는 노래 저장
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken(); // 노래 제목 문자열 개수
            String title = st.nextToken(); // 노래 제목
            
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<3; j++) {
                sb.append(st.nextToken());
            }
            String melody = sb.toString(); // 노래 첫 세 음
            
            if (map.containsKey(melody)) {
                // 같은 음이 두 개 이상이라는 의미 => "?" 저장
                map.put(melody, "?");
            } else {
                map.put(melody, title);
            }
        }
        
        // 노래 문제 출제
        for (int i=0; i<m; i++) {
            String s = br.readLine().replace(" ","");
            // 문제 맞추기
            if (map.containsKey(s)) {
                System.out.println(map.get(s));
            } else {
                System.out.println("!");
            }
        }
        
        br.close();
    }
}

공부한 내용정리

• String.split()보다 StringTokenizer가 더 빠르다. (다른방법 1 참고)
• 값이 중복될 수 있다고 해서 value로 지정할 수 있지만, key로 지정하여 중복된 것을 찾고 그에 맞는 value값을 지정할 수 있는 방법으로 탐색을 좀 더 최적화 할 수 있다.