[백준] 19637: IF문 좀 대신 써줘 - JAVA

26 Sep 2023 in Algorithm on 기타

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

풀이

N개의 문자열과 숫자가 주어진다.

해당 숫자 이하의 점수라면 해당 문자열이 칭호가 되는 것이다.

문자열과 점수를 배열에 저장해두고 M개의 점수가 나올 때마다

해당 배열을 이용해서 맞는 칭호를 출력해야 한다.

칭호의 개수 최대값이 10의 5제곱이기 때문에 앞에서부터 확인하면 시간초과가 발생한다.

따라서, 이분탐색을 통해 해당 구간에 점수가 포함되는지 확인해주었다.

---

메모리: 54040KB

시간: 520ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static class Node {
        String name;
        int score;

        public Node(String name, int score) {
            this.name = name;
            this.score = score;
        }
    }

    static Node[] arr;

    public static void main(String[] args) throws Exception {
        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());

        arr = new Node[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = new Node(st.nextToken(), Integer.parseInt(st.nextToken()));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(br.readLine());
            sb.append(makeName(a)).append("\n");
        }

        System.out.println(sb);
    }

    private static String makeName(int a) {
        int left = 0;
        int right = arr.length - 1;

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

            if (arr[mid].score < a) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return arr[left].name;
    }

}