[Java] 백준 19637번 : IF문 좀 대신 써줘

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

19637번: IF문 좀 대신 써줘

---

💡 문제 풀이

기본적인 이분탐색 문제이다.

 

칭호와 값의 매핑을 위해서 Map을 사용했고, 그중 비교가 빠른 HashMap을 사용했다.

중복을 제외해서 Map에 넣고 이분탐색을 위해 필요한 배열을 스트림으로 정렬해서 넣었다.

이후는 이분탐색으로 찾으면 된다!

 

시간복잡도는 아무리 커야 O(nlogn)이다.

✔️ 느낀 점

자바로 알고리즘을 푸는 건 너무 어렵다. 파이썬에 비해서 자료구조에 대해서 매우 엄격한 것 같다.

💻 코드

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

public class Main {
    static BufferedReader br = getBufferedReader();
    static BufferedWriter bw = getBufferedWriter();
    static Map<Integer, String> table = new HashMap<>();
    static int[] keys;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = getTokenizer();
        int n = getIntFromToken(st);
        int m = getIntFromToken(st);

        initSetup(n);
        solution(n, m);
    }

    private static void initSetup(int n) throws IOException {
        for (int i = 0 ; i < n ; i++) { 
            StringTokenizer st = getTokenizer();
            String title = getStringFromToken(st);
            Integer key = getIntFromToken(st);

            if (isNotDuplicated(key)) { 
                table.put(key, title);
            }
        }

        keys = getKeys();
    }

    private static void solution(int n, int m) throws IOException {
        for (int i = 0; i < m; i++) { 
            int input = getIntFromInput();
            String title = binarySearch(input); 
            write(title);
        }
        bw.flush();
    }

    private static String binarySearch(int target) {
        int start = 0;
        int end = keys.length - 1;
        int middle;

        while (start <= end) {
            middle = (start + end) / 2;
            if (target > keys[middle]) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        return getTitle(keys[start]);
    }

    private static String getTitle(Integer key) {
        return table.get(key);
    }

    private static int[] getKeys() {
        return table.keySet().stream()
                .mapToInt(Integer::intValue)
                .sorted()
                .toArray();
    }

    private static boolean isNotDuplicated(Integer key) {
        return !table.containsKey(key);
    }

    private static int getIntFromInput() throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private static int getIntFromToken(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    private static String getStringFromToken(StringTokenizer st) {
        return st.nextToken();
    }

    private static void write(String title) throws IOException {
        bw.write(title + "\n");
    }

    private static StringTokenizer getTokenizer() throws IOException {
        return new StringTokenizer(br.readLine());
    }

    private static BufferedReader getBufferedReader() {
        return new BufferedReader(new InputStreamReader(System.in));
    }

    private static BufferedWriter getBufferedWriter() {
        return new BufferedWriter(new OutputStreamWriter(System.out));
    }
}