백준 1620

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

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

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

        String input = br.readLine();

        StringTokenizer st = new StringTokenizer(input, " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map map = new HashMap();

        for (int i = 1; i <= n; i++) {
            int key = i;
            String value = br.readLine();

            map.put(key, value);
        }

        List<Object> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            list.add(br.readLine());
        }

        List<Object> result = new ArrayList<>();
        List<Map.Entry<Integer, String>> entries = new LinkedList<>(map.entrySet());
        entries.sort(Map.Entry.comparingByValue());


        for (int i = 0; i < list.size(); i++) {
            char ch = ((String) list.get(i)).charAt(0);
            if (Character.isDigit(ch)) {
                result.add(map.get(Integer.parseInt((String) list.get(i))));
            } else {

                int start = 0;
                int mid = 0;
                int end = entries.size() - 1;

                while (start <= end) {
                    mid = (start + end) / 2;
                    if (entries.get(mid).getValue().compareTo((String) list.get(i)) == 0) {
                        result.add(entries.get(mid).getKey());
                        break;
                    } else if (entries.get(mid).getValue().compareTo((String) list.get(i)) < 0) {
                        start = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }
                

            }
        }

        for (Object i : result) {
            System.out.println(i);
        }

    }
}

위 코드는 Map 한 개로 문제를 풀려고 했다.

Key에는 포켓몬의 번호를 value에는 포켓몬의 이름을 넣었다.

 

오박사가 문제를 냈을 때 포켓몬의 번호를 주었는지 이름으로 주었는지 판단하기 위해 아래의 코드를 사용했다.

char ch = ((String) list.get(i)).charAt(0);
            if (Character.isDigit(ch))

번호를 주어졌을 때 Map get 메소드를 통해 포켓몬의 이름을 가져온다.

포켓몬의 이름이 주어졌을 때 이름을 기준으로 사전순으로 저장된 List를 통해서 이진검색으로 포켓몬 번호를 찾는다.

 

하지만 1문제마다 이진 검색을 하기 때문에 시간이 오래 걸린다.

그래서 단순하게 생각해서 Map를 2개 만들었다.

포켓몬 번호가 Key인 Map,. 포켓몬 이름이 Key인 Map

오박사의 문제가 주어졌을 때 포켓몬 번호인지 포켓몬 이름인지 판단하고 적절한 Map에 적용시켜 get 메소드를 통해 답을 찾았다.

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

        String input = br.readLine();

        StringTokenizer st = new StringTokenizer(input, " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map numberIndexMap = new HashMap();
        Map nameIndexMap = new HashMap();

        for (int i = 1; i <= n; i++) {
            int key = i;
            String value = br.readLine();

            numberIndexMap.put(key, value);
            nameIndexMap.put(value, key);
        }

        List<Object> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            list.add(br.readLine());
        }

        List<Object> result = new ArrayList<>();

        for (Object o : list) {
            char ch = o.toString().charAt(0);
            if (Character.isDigit(ch)) {
                result.add(numberIndexMap.get(Integer.parseInt(o.toString())));
            } else {
                result.add(nameIndexMap.get(o.toString()));
            }
        }

        for (Object o : result) {
            System.out.println(o);
        }
    }
}