[BOJ] 좋은 구간

문제

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

A와 B는 양의 정수이고, A < B를 만족한다.
A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.
집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

풀이

우선 일반화를 시키는 과정을 거쳤다.
구간을 구하기 위해서 n의 위치를 케이스별로 나누었다.
구간이 n이 완전히 포함되는 경우와 왼쪽 구간에 n이 포함되는 경우 두가지이다.
말로 표현하면 좀 이상하지만
n이 7이라고 가정한다면
첫번째 케이스는 [1, 7], [2, 8], [4, 11] 이러한 경우이고,
두번째 케이스는 [7, 10], [7, 11], [7, 14]... 이러한 경우라고 생각하면 되겠다.

n보다 큰 수중 가장 작은수의 인덱스를 fistIndex라고 하면
fistIndex 이후의 값에는 [n, fistIndex], [n, fistIndex + 1]... 이러한 값만 올 수 있다.
따라서 두번째 값에 대한 갯수를 일반화 시키면 (arr[firstIndex] - n) - 1 이라는 결과가 나온다.
첫번재 경우는 fistIndex가 n보다 작은 경우들이다.
이때 갯수를 세는 법은 n보다 작은수중 배열 arr을 포함시키지 않는 값에서 같은 연산이 이루어진다.
즉, 4 7 15 24 30이라고 예를 들면

firstIndex는 (이해가 쉽도록 index말고 value값을 사용하겠다) 13이 된다.

첫번째 케이스의 경우는
[8, 10], [8, 11] ...[8, 14],
[9, 10], [9, 11]... [9, 14]...
이러한 식으로 이루어져 두번째 케이스가 다다를때 까지 이루어진다.
이를 일반화 시키면 (arr[firstIndex] - n) * (n - arr[firstIndex - 1] - 1)
이 된다.
한가지 더 고려해야 할 점은 firstIndex가 0일때 이다. 이때는 firstIndex - 1을 사용할 수없다.
이 경우는 첫번째 케이스가 n번까지 쭉 이루어 진 경우이므로 (arr[firstIndex] - n) * (n - 1)로 일반화 시킬 수 있다.

다른 풀이를 봤는데 브루트포스로 많이 푼 풀이가 보인다.
뭔가 규칙이 있을 것 같아서 파고 들었는데 풀이가 되서 나름 뿌듯???하다.
일반화 시키는 과정이 몇시간 걸린건 안비밀...

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(arr);
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        int firstIndex = 0;

        for(int i = 0; i < arr.length; i++) {
            if (n < arr[i]) {
                firstIndex = i;
                break;
            }
        }

        if (firstIndex == 0) {
            sum += (arr[firstIndex] - n) * (n - 1) ;
        } else {
            sum += (arr[firstIndex] - n) * (n - arr[firstIndex - 1] - 1);
        }
        sum += (arr[firstIndex] - n) - 1;

        if (sum < 0) {
            System.out.println(0);
        } else {
            System.out.println(sum);
        }
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%A2%8B%EC%9D%80%EA%B5%AC%EA%B0%84