[백준 - 1060번] 좋은 수 - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: 정렬, 우선순위 큐, 수학

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

정수 x를 포함하는 좋은 구간의 개수가 정수 y를 포함하는 좋은 구간의 개수보다 작으면 x는 y보다 더 좋다고 한다. x와 y를 포함하는 좋은 구간의 개수가 같거나, 구간의 개수가 둘 다 무한대와 같은 경우, 작은 수를 더 좋다고 한다.

집합 S가 주어지고, 이를 이용해 전체 정수를 더 좋은 수가 앞으로 오게 정렬했다고 가정하자. 앞에 오는 수 n개를 구해보자.

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

출력

상위 N개의 수를 공백으로 구분해 출력한다.

제한

• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000,000,000보다 작거나 같다.
• 1 ≤ n ≤ 100

풀이

집합 S가 주어지고, 이를 이용해 전체 정수를 더 좋은 수가 앞으로 오게 정렬했다고 가정하자. 앞에 오는 수 n개를 구해 출력해야 한다.

여기서 1 ~ 4 구간에서 나올 수 있는 가능한 모든 좋은 구간을 표현하면,

1 ~ 2, 1 ~ 3, 1 ~ 4
2 ~ 3, 2 ~ 4
3 ~ 4

이고,
1부터 4정수까지 포함하는 좋은 구간의 개수를 구하면,
1은 3개
2는 5개
3은 3개
4는 3개
라는 것을 알 수 있다.

각 정수의 포함하는 좋은 구간의 개수를 구하는 공식은 시작점과 끝지점을 알면, 구할 수 있다.
공식은 다음과 같다.

static long findIncludedSectionValue(int A, int B, int num) {
    return ((long) B - num) + (((long) B - (num - 1)) * (num - A));
}

이렇게 정수가 포함되는 구간의 개수를 구해보면, 패턴을 알 수 있는데,

각 구간에서(여기서 말하는 구간은 가장 큰 구간 1 ~ 4를 의미한다.)
항상 양쪽 끝 중 하나가 그 구간에서 가장 좋은 수가 된다는 것이다.

예를 들어 1 ~ 4에서는 1과 4중 하나가 다음은 2와 4중 하나가.. 이렇게 말이다.

그러면 각 구간마다 최선의 값을 pq에 하나씩 넣고, 가장 좋은 수를 poll()했을 때 현재 poll()한 값이 존재했던 구간에서 최선의 값을 pq에 채워넣는 방식으로, 답을 구할 수 있다.

pq의 정렬 조건은 포함하는 좋은 구간의 개수가 작은 순으로, 같다면 num이 작은 순으로 정렬하면 된다. 그러면 pq에는 좋은 수 순서로 정수가 나오게 된다.

예를 들어

3
5 11 18
9

이 예제를 보면, 구간은 1 ~ 4, 6 ~ 10, 12 ~ 17로 크게 나눌 수 있고,

이 각 구간에서는 또 많은 좋은 구간이 있을 것이다. 이를 전부 구할 필요는 없고, 공식을 알기 때문에 각 구간에서 양쪽 끝에 정수의 포함되는 좋은 구간의 개수를 비교해 하나씩만 pq에 유지해 주면 된다.

여기서 중요한 점은 입력에 5 11 18도 pq에 넣어줘야 하는데 이 값은 어떤 구간에도 포함되어 있지 않다. 그래서 0값으로 넣어주면 된다.

그리고 S가 2 3 4인 경우의 구간은 4 ~ 무한대 밖에 없지만, 구간이 없는 1같은 경우도 고려해줘야 한다.

이렇게 pq에 모든 값을 poll()했는데도, n이 남아있다면

마지막은 19 ~ 무한대에서 정수를 차례대로 answer에 붙이면 된다.
왜냐하면 19부터는 포함되는 좋은 구간의 개수가 무한대로 같기 때문에 더 작은 수가 우선이 된다.

소스 코드

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

//구간 class
class Interval {
    int A, B, lc, rc;
    Interval(int A, int B) {
        this.A = A;
        this.B = B;
        this.lc = A; //left cursor
        this.rc = B; //right curcor
    }
}

class IntegerInfo implements Comparable < IntegerInfo > {
    int ind; //어떤 구간에 정수인지.
    int num; //
    long v; //값.

    IntegerInfo(int ind, int num, long v) {
        this.ind = ind;
        this.num = num;
        this.v = v;
    }

    @Override
    public int compareTo(IntegerInfo o) {
        if (this.v < o.v) {
            return -1;
        } else if (this.v == o.v) {
            //같다면 더 작은 정수.
            if (this.num < o.num) {
                return -1;
            } else if (this.num > o.num) {
                return 1;
            }
        } else {
            return 1;
        }
        return 0;
    }
}

public class Main {
    static int L, n;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        L = Integer.parseInt(br.readLine());
        int[] S = new int[L];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < L; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(S); //오름차순 정렬
        n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        ArrayList < Interval > itvList = new ArrayList < > ();

        PriorityQueue < IntegerInfo > pq = new PriorityQueue < > ();
        //구간 넣기
        int left = 1;
        for (int i = 0; i < L; i++) {
            pq.add(new IntegerInfo(-1, S[i], 0));
            int right = S[i] - 1;
            if (left < right) {
                //조건을 만족한다면.
                itvList.add(new Interval(left, right));
            } else if (left == right) {
                //좋은 구간에 포함되는 값이 0임
                pq.add(new IntegerInfo(-1, left, 0));
            }
            left = S[i] + 1;
        }

        for (int i = 0; i < itvList.size(); i++) {
            int A = itvList.get(i).A;
            int B = itvList.get(i).B;
            pq.add(new IntegerInfo(i, A, findIncludedSectionValue(A, B, A)));
            itvList.get(i).lc += 1;
        }

        while (!pq.isEmpty()) {
            IntegerInfo intInfo = pq.poll();
            sb.append(intInfo.num).append(" ");
            n -= 1;
            if (n == 0) {
                break;
            }
            if (intInfo.ind != -1) {
                Interval itv = itvList.get(intInfo.ind);
                if (itv.lc <= itv.rc) {
                    long lcV = findIncludedSectionValue(itv.A, itv.B, itv.lc);
                    long rcV = findIncludedSectionValue(itv.A, itv.B, itv.rc);
                    if (lcV <= rcV) {
                        pq.add(new IntegerInfo(intInfo.ind, itv.lc, lcV));
                        itv.lc += 1;
                    } else {
                        pq.add(new IntegerInfo(intInfo.ind, itv.rc, rcV));
                        itv.rc -= 1;
                    }
                }
            }
        }

        if (n == 0) {
            System.out.println(sb.toString().trim());
        } else {
            //n이 아직 남아있다면.
            int start = S[L - 1] + 1;
            int end = start + n - 1;
            for (int i = start; i <= end; i++) {
                sb.append(i).append(" ");
            }
            System.out.println(sb.toString().trim());
        }

    }

    static long findIncludedSectionValue(int A, int B, int num) {
        return ((long) B - num) + (((long) B - (num - 1)) * (num - A));
    }
}