[JAVA] Map에서 value값에 대응하는 key값 찾는 방법? - 백준1620번

백준 1620번 문제

https://www.acmicpc.net/submit/1620/94655619

 

개요

첫째 줄에 도감에 수록되어 있는 포켓몬의 개수 N과 맞춰야 하는 문제의 개수 M이 주어진다.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어온다.

이후 총 M개의 줄에 맞춰야하는 문제가 입력으로 들어온다.

문제가 알파벳으로 들어오면, 포켓몬 번호를 출력

문제가 숫자로 들어오면, 포켓몬 번호에 해당하는 문자 출력

 

접근

value값(포켓몬 도감 번호)에 대응하는 key(포켓몬 이름)을 찾는 방법을 사용했다.

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input [] = br.readLine().split(" ");
        //입력 받을 포켓몬 수
        int countPokemon = Integer.parseInt(input[0]);
        //맞춰야할 정답 수
        int countQuestion = Integer.parseInt(input[1]);

        //번호와 포켓몬을 저장할 맵.
        Map <String, Integer> Encyclopedia = new HashMap<>();

        for(int i = 1; i <= countPokemon; i++){
            String pokemon = br.readLine();
            Encyclopedia.put(pokemon, i);
        }
        
        for(int i = 0; i < countQuestion; i++){
            String inputQuestion = br.readLine();
            //숫자 처리
            if(Character.isDigit(inputQuestion.charAt(0))){
                int num = Integer.parseInt(inputQuestion);
                for(Map.Entry<String, Integer> entry : Encyclopedia.entrySet()){
                    if(entry.getValue().equals(num)){
                        bw.write(entry.getKey() + "\n");
                    }
                }
            }
            else{ //문자 처리
                bw.write(Encyclopedia.get(inputQuestion) +"\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

시간초과 

 

Map에서 value로 key를 찾는 방식은 비효율적이다.

Java에서 Map은 본질적으로 key -> value 방향으로만 빠르게 작동하도록 설계되어 있다.

map.get(key) 는 O(1)이지만, 

value -> key는 지원하지 않아서, 전체를 순회해야 한다. 즉 최악의 경우 O(N)

 

---

해결방법

추가적인 저장공간을 사용.

Map을 사용하는 방법, 배열을 사용하는 방법

• 입력 처리를 try catch문을 사용하는 방법, Character.isDigit()를 사용하는 방법

위의 4가지 방법 중에서 배열, Character.isDigit()를 사용해 문제를 해결하였다.

 

---

배열을 사용하고, Character.isDigit()를 사용해 입력을 처리하는 방법

 

Character 클래스의 isDigit() 함수를 사용해 숫자인지 판별한다.

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input [] = br.readLine().split(" ");
        //입력 받을 포켓몬 수
        int countPokemon = Integer.parseInt(input[0]);
        //맞춰야할 정답 수
        int countQuestion = Integer.parseInt(input[1]);

        //번호와 포켓몬을 저장할 맵.
        Map <String, Integer> Encyclopedia = new HashMap<>();
        //번호에 대응하는 이름 저장할 배열
        String [] numberToName = new String[countPokemon + 1];

        for(int i = 1; i <= countPokemon; i++){
            String pokemon = br.readLine();
            Encyclopedia.put(pokemon, i);
            numberToName[i] = pokemon;
        }

        for(int i = 0; i < countQuestion; i++){
            String inputQuestion = br.readLine();
            if(Character.isDigit(inputQuestion.charAt(0))){ 
                int number = Integer.parseInt(inputQuestion);
                bw.write(numberToName[number] + "\n");
            }
            else{
                bw.write(Encyclopedia.get(inputQuestion) + "\n");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

---

 

다른 방법들의 코드와 성능을 분석한 글은 아래에서 확인할 수 있다.

 

https://0htmdwns.tistory.com/14

[JAVA] Map과 배열, try-catch와 Character.isDigit() 성능 분석 (+스택 트레이스)