[알고리즘/백준] #1059 좋은 구간

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

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

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

package sw_study.bj1059;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int L = sc.nextInt();
		
		int[] arr = new int[L];
		for(int i=0;i<L;i++) {
			arr[i]=sc.nextInt();
		}
		int n = sc.nextInt();
		
		Arrays.sort(arr);
		
		int answer=0;
		if(n<arr[0]) {
			answer=(arr[0]-n)*(n-1)+(arr[0]-n-1);
		}else {
			int a=0, b=0;
			for(int i=0;i<L;i++) {
				if(n==arr[i]) {
					answer=0;
					break;
				}
				if(arr[i]<n&&arr[i+1]>n) {
					a=arr[i];
					b=arr[i+1];
					answer=(b-n)*(n-a-1)+(b-n-1);
					break;
				}
			}
		}
		System.out.println(answer);
	}
}