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

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

1620번: 나는야 포켓몬 마스터 이다솜

 

Collection Framework를 이용해 어렵지 않게 풀 수 있는 문제

 

다만 정답률이 낮은 이유는 시간 제한 2초 때문인데 나도 첫 제출 때는 시간 제한으로 정답처리를 받지 못했던..

 

코드 자체는 복잡하지 않으니 코린이인 저보다는 다들 잘 작성하셨을거라 생각해

이번 글에서는 시간 제한을 해결한 과정에 대해 다뤄볼까 해요

 

 

---

 

문제 분석

지문이 많~~~~이 길긴한데 결국

N만큼 입력받아 저장하고 M만큼 저장된 데이터를 읽어와라

위 내용이 문제에서 요구하는 사항이네요

 

처음 이 문제를 읽으면 Map을 사용해야겠다는 생각이 가장 먼저 들죠?!

(더 좋은 방법이 있을 수도 있지만 저는 그랬다구요..)

 

그러면 Map Interface를 구현하는 HashMap, LinkedHashMap, TreeMap 세 가지 중 골라야할텐데..

문제를 보니 순서나 정렬이 필요없기 때문에 HashMap을 사용하면 될 거 같다는 생각이 들어 일단 코드를 작성해보

기 전에 잠시 ! 

 

HashMap을 통해 Key와 Value를 쌍으로 저장하는데,

N만큼 입력되는 값은 문자 또는 숫자가 주어진다는 점이 이 문제의 핵심이네요

 

그러면

(결과론적이지만)

1. HashMap 객체 두 개를

obj1 = Key : String, Value : Integer   /   obj2 = Key : Integer, Value : String

처럼 생성하여 입력값의 타입이 String이면 Integer값을, 입력값의 타입이 Integer이면 String 값을

get() 메서드를 통해 출력해주는 방법이 있을 수 있겠고요,

2. String 배열을 선언해 Integer값이 입력되면 배열 Index를 사용해 String값을 얻어오는 방식도 생각해 볼 수 있겠네요!

 

저는 처음에는 입력값이 숫자라면 entrySet을 통해 반복문을 통해 Value값에 대응하는 Key값을 출력하고자 했어요

---

제출 코드 1

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

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());

        int encyclopedia = Integer.parseInt(st.nextToken());
        int toCorrect = Integer.parseInt(st.nextToken());
        Map<String, Integer> pocketmonMap = new HashMap<>();

        for (int i = 1; i <= encyclopedia; i++) {
            pocketmonMap.put(br.readLine(), i);
        }
        for (int i = 0; i < toCorrect; i++) {
            // 숫자, 영어 구분
            String input = br.readLine();
            if (input.matches("^[a-zA-Z]*$")) {
                bw.write(pocketmonMap.get(input) + "\n");
                bw.flush();
            } else {
                for (Map.Entry<String, Integer> el : pocketmonMap.entrySet()) {
                    if (el.getValue().equals(Integer.parseInt(input))) {
                        bw.write(el.getKey() + "\n");
                        bw.flush();
                        break;
                    }
                }
            }
        }
        br.close();
        bw.close();
    }
}

위의 코드를 제출하니 시간 초과 ㅠㅠ

 

이 후 제일 처음 생각했던 부분은

정규표현식을 통해 입력값을 구분하는 방식이 시간이 많이 소요되지 않을까?
일치하는 값을 찾을 때까지 반복문을 도는 행위는 비효율적이다

라는 점이었어요

 

그래서 위에서 언급했던 방법 중 String 배열을 이용하고

문제 특성 상 포켓몬 이름은 반드시 영어라는 점을 이용해 입력값의 첫 문자가 문자 타입인지만 검사하도록 수정했어요

 

---

제출 코드2

						...
                        
        Map<String, Integer> pocketmonMap = new HashMap<>(encyclopedia);
        String[] names = new String[encyclopedia + 1];
        
        for (int i = 1; i <= encyclopedia; i++) {
            String input = br.readLine();
            pocketmonMap.put(input, i);
            names[i] = input;
        }

        for (int i = 0; i < toCorrect; i++) {
            String input = br.readLine();
            if (!Character.isDigit(input.charAt(0))) {
                bw.write(pocketmonMap.get(input) + "\n");
                bw.flush();
            } else {
                bw.write(names[Integer.parseInt(input)] + "\n");
                bw.flush();
            }
        }
        
						...

다행히 정답 처리를 받긴 했는데...

더 더 더 시간을 줄일 수 있지 않을까?..

 

그러고 보니 문제에서 값을 입력하면 바로 출력해줘야 한다는 조건이 명시되어 있지 않아

버퍼를 비워주는 행위를 반복문마다 수행할 필요가 없겠다는 생각이 들어서 flush를 반복문 바깥으로 옮겨보니

 

시간이 확 줄었네요

 

이 쯤에서 만족하려다가!! 조금 궁금한 점이 생겼어요

 

BufferedWriter를 통해 출력 vs StringBuilder를 통해 출력

 

둘 중 어떤게 조금 더 나은 방법일까 궁금해서 코드를 수정해보니

(해당 데이터 상으로는)매우 미미하지만 StringBuilder로 출력하는게 조금 더 시간적 이점이 존재하네요

 

검색해보니 둘의 차이는 거의 없다고 하니 사용하시기 편한 걸 사용해 문제를 해결해도 상관없을 듯~

 

 

 

 

 

끝