백준 26152 - 플래피 버드 스코어링

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

26152번: 플래피 버드 스코어링

 

* 문제 요약

플래피 버드는 장애물을 피해 최대한 멀리까지 도달하는 게임이다.

하나의 장애물을 피할때마다 1점씩 점수를 얻게 된다. 게임에는 총 N개의 장애물이 존재하고, i번째 장애물은 두 개의 장애물로 표현된다. 상단 장애물 끝 지점의 위치는 Ai로 나타내어지고, 하단 장애물 끝 지점의 위치는 Bi 로 나타내어진다.

플래피 버드 고수 세정이는 장애물이 어떤식으로 주어지든 플래피 버드를 조작해 피할 수 있다.

(단, 플래피 버드의 크기가 장애물의 틈새보다 클 경우에는 세정이도 장애물을 피하지 못한다.)

즉, 플래피 버드의 크기 w가 장애물의 틈새보다 클 경우에는 장애물을 피하지 못한다. 이때, 장애물을 피하지 못하면 게임이 바로 끝나게 된다.

여러 종류의 플래피 버드가 각 게임마다 주어질 때, 해당 플래피 버드를 가지고 몇 점까지 획득할 수 있는지 구하려고 한다.

세정이의 게임 스코어를 구해 출력해보자.

 

* 입력

첫 번째 줄에는 장애물의 갯수 N이 주어진다. (1 <= N <= 250,000)

두 번째 줄에는 상단 장애물의 위치 Ai 가 공백으로 구분되어 주어진다. (-10^9 <= Ai <= 10^9)

세 번째 줄에는 하단 장애물의 위치 Bi 가 공백으로 구분되어 주어진다. (-10^9 <= Bi <= 10^9)

이때, 주어지는 입력은 Bi <= Ai 임이 보장된다.

네 번째 줄에는 플레이할 플래피 버드의 갯수 Q가 주어진다. (1 <= Q <= 250,000)

다섯 번째 줄에는 각 플래피 버드의 크기 wi 가 주어진다. (1 <= wi <= 10^9)

 

* 출력

각 플래피 버드별로 세정이가 얻을 수 있는 최대 게임 스코어를 각 줄마다 하나씩 출력한다.

 

* 예시

 

* 해결 과정

- 틀렸던 방법(시간 초과)

Ai - Bi을 연산한 값과 현재 장애물의 입력 순서(인덱스)를 필드로 하는 객체를 만들어서 해당 객체의 배열을 만들고 해당 배열에 각 장애물들에 대한 정보를 객체화하여 저장했다.

(해당 객체의 경우 Comparable 인터페이스를 구현시켜서 compareTo() 메소드를 오버라이드 한 다음, 정렬시 장애물 A와 B사이의 틈새값을 기준으로 오름차순 정렬되게끔 코드를 작성해줬다.)

배열에 각 장애물 사이의 틈새값과 위치 정보를 다루는 객체들이 저장되고 나면 해당 배열을 오름차순 정렬해주었다.

 

이후 플래피 버드들의 크기값이 입력되고 나면 각 크기값을 기준으로 앞전에 정렬된 배열에 대해 lowerBound 형식으로 이분탐색을 수행하여 각 장애물들의 틈새값이 현재 플래피 버드의 크기값보다 작은것들 중 틈새값이 가장 큰 객체가 있는 위치를 찾아낸 다음, 객체 배열의 첫 번째 인덱스에서 부터 해당 위치까지 객체들의 틈새값이 현재 플래피 버드의 크기보다 작다고 할 수 있으므로 (틈새값을 기준으로 오름차순 정렬되어 있기 때문에) 해당 범위안에 있는 값들 중 장애물 자체의 인덱스가 가장 앞서 있는 객체를 다음과 같이 찾아주었다.

 

처음엔 배열의 첫 번째 인덱스부터 앞에서 찾은 인덱스 위치까지 순차탐색을 진행하며 현재 탐색중인 객체의 인덱스 값과 이전에 탐색한 인덱스 값을 비교하여 더 작은 값으로 초기화해주는 방식으로 장애물의 입력 데이터 상에서 가장 앞서있는 인덱스를 찾아주었더니 시간초과라는 결과를 반환받았다.

//  birdSize 보다 작은 값들 중 가장 작은 인덱스 찾기
            int min = Integer.MAX_VALUE;
            for(int index = 0; index < start; index++){
                min = Math.min(min, birds[index].index);
            }

            if(min == Integer.MAX_VALUE){
                // 이곳에 있는 코드가 실행된다면 현재 birdSize 보다 틈의 크기가 작은 장애물이 없다는 뜻
                // 즉, 장애물 끝까지 갈 수 있다.
                bw.write(n + "\n");
            } else {
                bw.write(min + "\n");
            }

 

그래서 이번엔 배열의 첫 번째 인덱스에서 부터 앞에서 찾은 인덱스 위치까지의 범위를 Arrays.copyofRange() 메소드를 통해 복사해서 새로운 배열을 만들어낸 다음, 해당 배열에 있는 객체들을 인덱스 값을 기준으로 오름차순 정렬되게끔 코드를 작성해주었었다.

그러나 이 역시 시간초과라는 결과를 반환받았다.

// birdSize 보다 작은 값들 중 가장 작은 인덱스 찾기
            // birdSize 보다 작은 장애물들을 따로 복사해 다른 배열에 저장
            if (start == 0) {
                bw.write(n + "\n");
            } else {
                Bird[] indexArray = Arrays.copyOfRange(birds, 0, start);

                // index 기준 재정렬
                Arrays.sort(indexArray, new Comparator<Bird>() {
                    @Override
                    public int compare(Bird arg0, Bird arg1) {
                        return arg0.index - arg1.index;
                    }
                });

                bw.write((indexArray[0].index) + "\n");
            }

 

이후 몇 시간을 더 고민해봐도 위의 두가지 방법 외에는 도저히 답을 찾아낼 방법이 떠오르지 않아 결국 다른 사람의 풀이를 찾아보았다.

 

- 통과된 풀이법

장애물 A와 B사이의 틈새값을 따로 배열에 저장해준 다음 단조감소(집합이 갈수록 점점 같거나 작아진다.) 원리를 이용해 다음의 조건에 맞춰 배열을 다시 초기화 해주었다.

- 배열의 1번째 인덱스에서 부터 마지막 인덱스까지 반복문을 통해 탐색하는 도중, 현재 인덱스 값이 이전의 인덱스 값보다 큰 경우 현재 인덱스 값을 이전 인덱스의 값으로 초기화시켜준다.

(오른쪽에 있는 인덱스 값이 왼쪽에 있는 인덱스의 값 보다 크다면 오른쪽에 있는 인덱스 값을 왼쪽 인덱스와 같은 값으로 초기화)

 

위의 조건을 거치면 배열은 자연스레 내림차순 정렬된 모습을 가지게 되는데, 원활한 이분탐색을 위해 배열의 각 인덱스 값에 -1을 곱해서 오름차순 정렬의 형태가 되게끔 해준다.

이후 플래피 버드의 크기값이 입력으로 들어오면 해당 크기값에도 -1을 곱해준 후 다음과 같이 이분탐색을 수행해준다.

(UpperBound 방식의 이분탐색, 배열의 각 값에 -1을 곱해주었으므로 실제로는 birdSize 보다 작은 값의 정확한 위치를 찾아주기 위해 UpperBound 방식의 이분탐색을 수행해주었다.)

1. start 를 0, end 를 n(장애물의 갯수)으로 초기화한다.

2. start < end 조건을 만족하는 동안 다음과 같이 반복문을 수행한다.

  - mid 를 (start + end) / 2 로 초기화해준다.

  - 현재 입력받은 플래피 버드의 크기(birdSize) 값이 배열의 mid 인덱스 값보다 크거나 같다면 start 를 mid + 1 로 초기화해준다.

  - 그렇지 않다면 end를 mid 로 초기화해준다.

3. 위의 반복문이 끝나고 나면 start(birdSize 에 -1을 곱해준 값 보다 큰 값이 최초로 나타난 위치, 실제로는 birdSize 보다 더 작은값이 처음으로 나타나는 위치이다.) 값을 출력해준다.

 

* 코드

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 NumberFormatException, IOException {
        new Main().solution();
    }

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

        int n = Integer.parseInt(br.readLine());

        String[] inputA = br.readLine().split(" ");
        String[] inputB = br.readLine().split(" ");
        // 장애물 틈새값들을 저장하기 위한 배열 선언 및 틈새값 저장
        int[] termArray = new int[n];
        for (int i = 0; i < termArray.length; i++) {
            termArray[i] = Integer.parseInt(inputA[i]) - Integer.parseInt(inputB[i]);
        }
        // 단조감소 처리
        for (int i = 1; i < termArray.length; i++) {
            if (termArray[i] > termArray[i - 1]) {
                termArray[i] = termArray[i - 1];
            }
        }
        // 단조감소시 내림차순으로 정렬되므로 각 항에 -1을 곱하여 오름차순 정렬로 변형
        for (int i = 0; i < termArray.length; i++) {
            termArray[i] *= -1;
        }

        // 오름차순으로 변형된 배열을 대상으로 이분탐색을 수행하여 최초로 현재 birdSize * -1 한 값 보다
        // 큰 값이 나타나는 위치를 찾는다.(UpperBound)
        int birdCount = Integer.parseInt(br.readLine());
        String[] inputBird = br.readLine().split(" ");
        for (int i = 0; i < birdCount; i++) {
            int birdSize = Integer.parseInt(inputBird[i]) * -1;

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

                if (birdSize >= termArray[mid]) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            bw.write(start + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

단조감소 원리를 사용해야함을 몰랐기에 스스로 풀기 힘겨웠던 문제, 확실히 이분탐색으로 분류되는 문제라고 해도 백준 실버1 이상의 난이도를 가진 문제부터는 더 이상 이분탐색만으로 문제를 풀 수는 없는것 같다.