Algorithm/Java

[백준/JAVA] 1620번: 나는야 포켓몬 마스터 이다솜

dbfl9911 2024. 10. 22. 16:05
반응형

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

[ 오답 노트 ]

❌ 기존 오답 코드

// https://www.acmicpc.net/problem/1620
package Data_Structure2.나는야포켓몬마스터이다솜;

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()); // 26
        int M = Integer.parseInt(st.nextToken()); // 5
        StringBuilder sb = new StringBuilder();

        HashMap<Integer, String> hm = new HashMap<>();
        for(int i = 1; i <= N; i++) {
            hm.put(i, br.readLine());
        }

        for(int j = 0; j < M; j++) {
            for(int i : hm.keySet()) {
                // 문자열이라면 숫자로
                if(br.readLine().equals(hm.get(i))) {
                    sb.append(i).append('\n');
                }else { // 숫자라면 문자열로
                    sb.append(hm.get(i)).append('\n');
                }
            }
        }
        System.out.println(sb);
    }
}

📌 기존 코드의 문제점

  1. 중복 반복 : 문제의 개수(M)만큼의 반복문 안에서, hm.keySet()을 다시 반복하며 모든 키 값을 탐색하여 매번 if-else 조건을 확인합니다. 이는 매우 비효율적이며 N과 M의 값이 커질수록 속도가 급격히 느려집니다.
  2. 단일 HashMap만 사용: 포켓몬 번호로 이름을 찾기 위한 HashMap만 사용하여, 문자열(포켓몬 이름)으로 번호를 찾기 위한 과정이 어렵고 비효율적입니다. 문자열로 번호를 찾아야 할 때 hm.keySet()을 전부 탐색하여야 하기 때문입니다.
  3. 비효율적인 조건 검사: br.readLine().equals(hm.get(i)) 방식은 매번 모든 keySet()을 탐색해야 하므로 효율이 떨어집니다. 단일 HashMap으로 두 가지 방식의 검색을 동시에 지원하기가 어렵습니다.

 

[ 정답 코드 & 올바른 풀이 ]

 

📌 정답 코드

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()); // 26
        int M = Integer.parseInt(st.nextToken()); // 5
        StringBuilder sb = new StringBuilder();

        // 번호 -> 이름
        HashMap<Integer, String> hm1 = new HashMap<>();
        // 이름 -> 번호
        HashMap<String, Integer> hm2 = new HashMap<>();

        for(int i = 1; i <= N; i++) {
            String s = br.readLine();
            hm1.put(i, s);
            hm2.put(s, i);
        }

        for(int j = 0; j < M; j++) {
            String s = br.readLine();
            // 첫문자가 숫자라면
            if(Character.isDigit(s.charAt(0))) {
                // 문자열 출력
                sb.append(hm1.get(Integer.parseInt(s))).append('\n');
            } // 첫문자가 문자라면
            else{
                // 숫자 출력
                sb.append(hm2.get(s)).append('\n');
            }

        }
        System.out.println(sb);
    }
}

 

 

📌 개선된 접근 방법

  1. 두 개의 HashMap 사용:
    • hm1은 번호로 이름을 찾을 때 사용하고, hm2는 이름으로 번호를 찾을 때 사용하여 각각 최적화된 구조로 접근합니다.
    • 각각의 HashMap에 O(1)의 시간 복잡도로 접근 가능해 문제를 빠르게 해결할 수 있습니다.
  2. 조건문 최적화:
    • 문자열이 숫자인지 문자인지 확인할 때 Character.isDigit() 메서드를 사용
    • s의 첫 번째 문자가 숫자인 경우 Character.isDigit(s.charAt(0))를 통해 쉽게 확인
  3. StringBuilder 사용으로 출력 최적화:
    • 모든 결과값을 StringBuilder에 추가한 후 한 번에 출력하여 성능을 향상시켰습니다. 이는 많은 입력과 출력을 다룰 때 효과적입니다.
반응형