[BOJ] 1059 좋은 구간 - JAVA

1. 문제

1059번: 좋은 구간

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

---

2. 풀이

1.  S를 입력받고 정렬한다.

2.  n이 S에 포함되었다면 좋은 구간은 없다. 0을 출력하고 끝낸다.

3.  n을 포함하는 구간을 n기준으로 둘로 나눠서 구한다.

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

public class BOJ_1059_좋은구간 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int L = Integer.parseInt(in.readLine());
      StringTokenizer st = new StringTokenizer(in.readLine());
      int[] S = new int[L];
      for(int i=0;i<L;i++) S[i] = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(in.readLine());

      Arrays.sort(S);
      int idx = Arrays.binarySearch(S,N);
      if(idx>=0){
         System.out.println(0);
         return;
      }

      idx = -idx-1;

      if(idx==0){
         System.out.println((N-1)*(S[0]-N-1)+(N-1)+(S[0]-N-1));
      }else{
         System.out.println((N-S[idx-1]-1)*(S[idx]-N-1)+(N-S[idx-1]-1)+(S[idx]-N-1));
      }

   }
}

---

3. 결과

마지막 식 세우느라 오래걸렸다.