백준 19637 - IF문 좀 대신 써줘 (자바 - 이분탐색)

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

19637번: IF문 좀 대신 써줘

 

* 문제 요약

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

if power <= 10000
 print WEAK
else if power <= 100000
 print NORMAL
else if power <= 1000000
 print STRONG

혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.

 

* 입력

첫 번째 줄에는 칭호의 갯수 N (1 <= N <= 10^5) 과 칭호를 출력해야 하는 캐릭터들의 갯수 M (1 <= M <= 10^5) 이 빈칸을 사이에 두고 주어진다. (1 <= N, M <= 10^5)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1이상, 11이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 10^9 이하의 음이 아닌 정수가 주어진다.

칭호는 전투력 상한값의 비내림차순으로 주어진다.

N+2번째 줄 부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

 

* 출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의, 전투력으로 출력할 수 있는 칭호가 여러개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

 

* 예시

 

* 해결 과정

처음에 주어지는 칭호와 전투력 상한값을 대상으로 이분탐색을 수행해주어야 한다. 칭호와 전투력의 입력 데이터가 오름차순으로 주어진다는 점에서 이것을 대상으로 이분탐색을 해야한다고 생각하는 것이 타당하다.

다만, 칭호는 다르더라도 전투력 수치는 중복이 존재할 수 있으므로, 이를 감안하여 중복이 존재할 때 해당값이 최초로 등장하는 인덱스를 찾아야 하는것을 유념하자.

 

각 캐릭터들의 전투력에 대한 입력이 주어졌을 때, 이를 따로 저장해두거나 할 필요 없이 입력이 들어오는대로 즉시 칭호와 전투력값을 대상으로 이분탐색을 수행해서 어떤 칭호를 주면 되는지 찾아주면 된다.

일단 칭호와 전투력의 경우 객체화 시켜서 각 데이터를 저장하고 이를 객체 배열에 입력 순서대로 저장해주자.

어차피 오름차순으로 입력이 들어오므로 따로 Comparable 인터페이스를 구현해서 compareTo() 메소드를 오버라이드해와 직접 코드를 작성해주는등 객체의 오름차순 정렬을 위한 일련의 과정들이 필요가 없다.

이렇게 객체 배열에 저장된 칭호와 전투력 값을 대상으로 다음과 같이 이분탐색을 수행해준다.

1. start 는 0, end 는 n으로 초기화한다.

2. start < end 조건을 만족하는 동안 다음과 같은 로직으로 반복을 수행한다.

  - mid 를 (start + end) / 2 값으로 초기화한다.

  - 현재 입력받은 캐릭터의 전투력이 객체 배열에서 mid 인덱스에 해당하는 값(객체)이 가지고 있는 전투력 상한 보다 크다면 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄인다.

  - 반대로 현재 입력받은 캐릭터의 전투력이 객체배열에서 mid 인덱스에 해당하는 값(객체)이 가지고 있는 전투력 상한보다 작거나 같다면 end 를 mid 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄인다.

3. 반복문이 끝나고 나면 객체 배열에서 최종적으로 초기화된 start 인덱스에 해당하는 값(객체)이 가지고 있는 칭호를 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        Combat[] combatArray = new Combat[n];
        for (int i = 0; i < combatArray.length; i++) {
            input = br.readLine().split(" ");
            combatArray[i] = new Combat(input[0], Long.parseLong(input[1]));
        }

        for (int i = 0; i < m; i++) {
            long combatScore = Long.parseLong(br.readLine());

            int start = 0;
            int end = n;
            // lowerBound
            while (start < end) {
                int mid = (start + end) / 2;

                if (combatScore > combatArray[mid].combatScore) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }

            bw.write(combatArray[start].style + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

class Combat {
    String style;
    long combatScore;

    public Combat(String style, long combatScore) {
        this.style = style;
        this.combatScore = combatScore;
    }
}

 

입력받은 칭호와 전투력 상한을 객체화하여 배열로 저장해준 다음, 해당 배열을 대상으로 이후에 입력받는 캐릭터들의 전투력에 맞는 상한을 가진 칭호를 절반씩 범위를 줄여가며 찾았으므로 이분탐색 문제에 해당된다.