[알고리즘] 백준 19637 IF 문 좀 대신 써줘

www.acmicpc.net/problem/19637

19637번: IF문 좀 대신 써줘

문제설명

문제는 되게 간단하다.

 

주어진 Stat에 맞는 칭호를 출력하면 된다. 문제에서 주어진 if문을 보면 이해가 아주 잘 될 것이다.

 

해결과정

시간이 엄청 빡빡하다.

 

범위가 그래도 좁아보여서 완탐으로 풀어봤는데 바로 시간초과가 떴다.

 

매 유저스텟마다 칭호와 함께 주어진 스텟값을 INDEX값을 통해 이진탐색을 돌린다.

 

심지어 다 풀고 채점했는데 계속 틀렸길래 검색해보니 StringBuilder를 사용하지 않으면 또 시간이 터진다.

 

여러모로 되게 빡빡한 문제였다. 스트링빌더를 쓰는 습관을 들여야 될 것 같다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Main {

    static int m;
    static int n;
    static List<Item> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            list.add(new Item(st.nextToken(), Integer.parseInt(st.nextToken())));
        }

        for (int i = 0; i < m; i++) {
            s = br.readLine();
            sb.append(list.get(binarySearch(Integer.parseInt(s))).name).append('\n');
        }

        System.out.println(sb.toString().trim());
    }

    static int binarySearch(int stat) {

        int userStat = stat;
        int left = 0;
        int right = list.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (userStat <= list.get(mid).value) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return right + 1;
    }

    static class Item {
        String name;
        int value;

        public Item(String name, int value) {
            this.name = name;
            this.value = value;
        }
    }
}