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

 

 

 문제가 너무 길어서 핵심적인 부분만 올린다. 그냥 보기에는 HashMap<이름, 번호>을 사용해서 간단하게 할 수 있어 보였다. 하지만 시간초과가 5번 나오고 정신을 다시 차렸다.

 

 

 

시간복잡도를 줄이고 시간초과에서 벗어나기 위해 

 

 Scanner를 사용하던 기존 방식에서 BufferReader와 StringTokenizer를 사용한 방식으로 바꾸고.

 시간복잡도를 O(n)으로 줄이기 위해 입력받은 문제가 정수인지 문자열인지 판별하기 위해 Exception을 사용했다.

 또한 HashMap<이름, 번호>한 개를 사용하는 대신 HashMap<이름, 번호>와 HashMap<번호, 이름>을 사용해 데이터를 저장했다. 

 

 

 

 

 

 

 

 

우선 입력을 받았다. 

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());//질문의 수
String name;//입력받을 포켓몬 이름
String question;//질문
HashMap<String, Integer> pokemon_1 = new HashMap<>();//이름 - 번호 도감
HashMap<Integer, String> pokemon_2 = new HashMap<>();//번호 - 이름 도감
int index = 1;//도감 번호
boolean isNum;//입력이 숫자인지 아닌지 판별
LinkedList<String> answer= new LinkedList<>();//정답지


//도감을 입력받는다
for(int i = 0; i<n; i++)
{
    name = br.readLine();
    pokemon_1.put(name, index);
    pokemon_2.put(index, name);
    index++;
}

 

 

 

 

 

 

 

 다음은 질문에 대한 답 저장과 출력이다. Int 자료형으로 질문을 변환하는 코드를 작성했다.

예외 발생 시 문자열이 정수로 이루어진 것이 아니라는 의미이기 때문에 catch에서 isNum을 false로 해 주었다.

 

 질문이 문자인지 숫자인지 판별되었다면 그에 맞게 HashMap에서 데이터를 꺼내왔다. 처음에는 keySet과 반복문을 통해서 꺼내왔었는데 시간복잡도도 줄이고 코드도 간결하게 하기 위해 그냥 get을 썼다.

//질문에 대한 답을 정답지에 저장한다
for(int i = 0; i<m; i++)
{
    question = br.readLine();

    //질문이 숫자인지 문자인지 판별
    try {
        Integer.parseInt(question);//실패 시 NumberFormatException 발생(question 이 문자열이라는 것을 나타냄)
        isNum = true;
    }
    catch (NumberFormatException e) {
        isNum = false;
    }

    //질문이 숫자인 경우
    if(isNum)
    {
        answer.add(pokemon_2.get(Integer.parseInt(question)));
    }
    //질문이 문자열인 경우
    else
    {
        answer.add(String.valueOf(pokemon_1.get(question)));
    }
}

while(!answer.isEmpty())
{
    System.out.println(answer.pop());
}

 

 

 

 

<전체 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());//질문의 수
        String name;//입력받을 포켓몬 이름
        String question;//질문
        HashMap<String, Integer> pokemon_1 = new HashMap<>();//이름 - 번호 도감
        HashMap<Integer, String> pokemon_2 = new HashMap<>();//번호 - 이름 도감
        int index = 1;//도감 번호
        boolean isNum;//입력이 숫자인지 아닌지 판별
        LinkedList<String> answer= new LinkedList<>();//정답지


        //도감을 입력받는다
        for(int i = 0; i<n; i++)
        {
            name = br.readLine();
            pokemon_1.put(name, index);
            pokemon_2.put(index, name);
            index++;
        }


        //질문에 대한 답을 정답지에 저장한다
        for(int i = 0; i<m; i++)
        {
            question = br.readLine();

            //질문이 숫자인지 문자인지 판별
            try {
                Integer.parseInt(question);//실패 시 NumberFormatException 발생(question 이 문자열이라는 것을 나타냄)
                isNum = true;
            }
            catch (NumberFormatException e) {
                isNum = false;
            }

            //질문이 숫자인 경우
            if(isNum)
            {
                answer.add(pokemon_2.get(Integer.parseInt(question)));
            }
            //질문이 문자열인 경우
            else
            {
                answer.add(String.valueOf(pokemon_1.get(question)));
            }
        }

        while(!answer.isEmpty())
        {
            System.out.println(answer.pop());
        }
    }
}