[백준 1620] 나는야 포켓몬 마스터 이다솜(Java)

나는야 포켓몬 마스터 이채림

 

---

🚨 문제 상황 1

Java에서 HashMap은 키-값 쌍으로 데이터를 저장하는 자료구조로

주로 키를 사용해 값을 검색하는데 최적화되어 있다.

 

위에 코드를 보면 값으로 키를 검색해야 하는 상황이 생긴 것을 확인핑.

 

🍧 해결법 1

entrySet() 사용을 사용하면 된다.

 

🍉 코드 1

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 번호, 이름 저장
        HashMap<Integer, String> map = new HashMap<>();
        for(int i=1; i<=n; i++) {
            String str = br.readLine();
            map.put(i, str);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<m; i++) {
            String answer = br.readLine();
            if(isNumber(answer)) {
                sb.append(map.get(Integer.parseInt(answer))).append("\n");
            } else {
                for(Map.Entry<Integer, String> entry : map.entrySet()) {
                    if(entry.getValue().equals(answer)) {
                        sb.append(entry.getKey()).append("\n");
                        break;
                    }
                }
            }
        }
        System.out.println(sb);
    }

    // 숫자인지 확인하는 메서드
    private static boolean isNumber(String str) {
        try {
            Integer.parseInt(str);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

 

 

🚨 문제 상황 2

위에 코드 제출한 상황

엥

 

 

🍧 해결법 2

시간 초과가 발생한 이유는 HashMap을 사용했음에도 값으로 키를 찾는 과정에서

for(Map.Entry<Integer, String> entry : map.entrySet()) 루프를 사용했기 때문이다.

이 루프는 HashMap의 모든 값을 순회하면서 값을 비교하므로

만약 입력 크기가 크다면 시간 초과가 발생할 가능성이 높다.

 

값으로 키를 빠르게 찾기 위해, HashMap을 두 개 사용하는 것이 가장 효율적이다.

하나는 번호 -> 이름 저장 (HashMap<Integer, String>)

다른 하나는 이름 -> 번호 저장(HashMap<String, Integer>)

 

🍉 최종 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 번호 -> 이름 맵
        HashMap<Integer, String> mapNumToName = new HashMap<>();
        // 이름 -> 번호 맵
        HashMap<String, Integer> mapNameToNum = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            String str = br.readLine();
            mapNumToName.put(i, str);
            mapNameToNum.put(str, i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String answer = br.readLine();
            if (isNumber(answer)) {
                // 숫자인 경우 번호로 이름 찾기
                sb.append(mapNumToName.get(Integer.parseInt(answer))).append("\n");
            } else {
                // 이름으로 번호 찾기
                sb.append(mapNameToNum.get(answer)).append("\n");
            }
        }
        System.out.println(sb);
    }

    // 숫자인지 확인하는 메서드
    private static boolean isNumber(String str) {
        try {
            Integer.parseInt(str);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

 

훠얼씬 보기 깔끔핑 해졌다 ㅎㅎ