[Java] 백준 21318 - 피아노 체조

Baekjoon_21318 - 피아노 체조

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

문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 10^9 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.

시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 x와 y를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?

입력

첫 번째 줄에 악보의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에 1번 악보부터 N번 악보까지의 난이도가 공백을 구분으로 주어진다.

세 번째 줄에 질문의 개수 Q(1 ≤ Q ≤ 100,000)이 주어진다.

다음 Q개의 줄에 각 줄마다 두 개의 정수 x, y(1 ≤ x ≤ y ≤ N)가 주어진다.

출력

x번부터 y번까지의 악보를 순서대로 연주할 때, 몇 개의 악보에서 실수하게 될지 0 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

---

해결방법

• 단순히 x부터 y번 까지 배열을 돌며 arr[i] > arr[i+1] 이면 cnt++ 로 해결하려 한다면 시간 초과가 날 것이다.
  • 만약 x = 0, y = N 이라면 시간복잡도는 O(NQ) 가 되므로 0.5초 안에 해결할 수 없다.
• 따라서 실수 횟수의 누적합을 저장할 result 배열을 따로 만들어둔다.
  • 입력으로 주어지는 arr 배열을 돌며 arr[i] > arr[i+1] 이라면 result[i]에 result[i - 1] + 1을, 그렇지 않다면 result[i - 1]의 값을 저장하는 것이다.
  • 이렇게 따로 실수의 누적합 배열을 따로 저장해두면, Q번 도는 반복문 안에서 따로 또 반복문을 돌 필요 없이 result 배열에서 값만 꺼내와 단순 계산만 하면 된다.

코드

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

public class Baekjoon_21318 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] result = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr[0] = 0;
        result[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                result[i] = result[i - 1] + 1;
            } else {
                result[i] = result[i - 1];
            }
        }
        if (arr[n - 1] > arr[n]) {
            result[n] = result[n - 1] + 1;
        } else {
            result[n] = result[n - 1];
        }

        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            String[] arr2 = br.readLine().split(" ");
            int x = Integer.parseInt(arr2[0]);
            int y = Integer.parseInt(arr2[1]);

            int answer = result[y] - result[x];

            System.out.println(answer);
        }

    }
}