[백준 1059] 좋은 구간

문제 링크 : https://www.acmicpc.net/problem/1059

이 문제는 스택과 우선 순위 큐를 이용하여 풀 수 있습니다. 이 문제의 경우 실버4 문제치고 푸는데 개인적으로 어려웠던 문제입니다. 먼저 이 문제를 좀 더 간단하게 요약하면 "A와 B 사이의 수 중 주어진 수 M을 반드시 포함하는 집합의 수"를 구하는 것과 같습니다. 이 경우는 크게 3가지가 존재합니다.

1. M과 A 사이의 수 중 M을 반드시 포함하는 수의 집합
2. M과 B 사이의 수 중 M을 반드시 포함하는 수의 집합
3. 1의 집합의 수와 2의 집합의 수를 모두 포함하는 수의 집합

각각을 구하는 경우는 문제의 조건을 파악하면 쉽게 풀 수 있습니다. 문제에서 구하고자 하는 집합 내의 원소의 개수는 "구간 내의 모든 정수"가 존재해야 하므로 바꿔말하면 "출발점과 도착점이 주어지면 이에 대응하는 집합은 반드시 하나"가 됩니다. 즉 1번과 2번의 경우는 쉽게 말하면 각각 "M과 A 사이의 수의 개수", "M과 B 사이의 수의 개수"가 됩니다.

3번의 경우 1과 2의 곱과 같습니다. 두 집합의 수를 모두 포함한다는 뜻은 바꿔말하면 두 집합에서 각각 출발점과 도착점을 뽑는 경우의 수와 같기 때문에 각 집합의 개수의 곱이 곧 두 집합의 수를 모두 포함하는 수입니다.

그렇다면 M이 사이에 있는 A와 B는 어떻게 구할까요? 여러 가지 방법이 있겠지만 저는 스택과 우선 순위 큐를 이용했습니다. 우선 순위 큐의 정렬 특징을 이용하여 주어진 집합을 오름차순 정렬한 후 M보다 peek가 클 때까지 값을 하나씩 뽑습니다. 이 때 M보다 작은 경우는 스택에 쌓아 스택의 peek에는 M보다 작은 수 중 최댓값이 저장되게 되며, 큐의 peek에는 M보다 큰 수 중 최솟값이 저장되게 됩니다. 즉 M이 사이에 존재하는 A와 B가 구해지게 됩니다.

여기서 주의할 점은 예외사항 처리입니다. 크게 3가지 경우가 존재합니다.

1. 스택이 비어 있는 경우 (M이 집합의 최솟값보다 작을 경우)
2. 큐가 비어 있는 경우 (M이 집합의 최댓값보다 클 경우)
3. M이 집합의 원소와 같을 경우

1번의 경우 M이 가장 작아 왼쪽의 값이 의미가 없기 때문에 A를 0, B를 큐의 peek값으로 설정하면 됩니다. 2번의 경우 M이 가장 커 오른쪽의 값이 의미가 없기 때문에 B를 최댓값(1000보다 큰 수면 됩니다), A를 스택의 peek값으로 설정하면 됩니다. 3번의 경우 문제에서 요구하는 조건이 절대 만족할 수 없기 때문에 0을 출력합니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            int val = Integer.parseInt(st.nextToken());
            queue.add(val);
        }
        int M = Integer.parseInt(br.readLine());

        int left=0,right=Integer.MAX_VALUE;
        Stack<Integer> stack = new Stack<>();
        while(queue.peek() <= M){
            if(queue.peek() == M){
                System.out.println(0);
                System.exit(0);
            }
            else{
                stack.add(queue.poll());
                if(queue.isEmpty()) break;
            }
        }

        if(stack.isEmpty()) right = queue.peek();
        else if(queue.isEmpty()) left = stack.peek();
        else{
            left = stack.peek();
            right = queue.peek();
        }

        int cntL = M - left -1;
        int cntR = right - M -1;

        System.out.println(cntL + cntR + cntL*cntR);
    }
}