Baekjoon 1059 좋은 구간 JAVA

1059번: 좋은 구간

문제

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

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

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

입력

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

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

풀이

주어지는 S는 순서가 있는 배열이 아닌 정수 집합이다. 그러기에 정렬을 해도 데이터의 내용에는 변화가 없다.

n이 있는 사이에 있는 값을 찾기 위해서, n이 가장 작은 값보다 작은 경우에는

1부터 S까지의 범위를 탐색하기에, 입력되는 S에 1이 없더라고 1부터 탐색을 해야한다.

 

코드 참고

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int l=Integer.parseInt(br.readLine()), ans=0;
		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);
		int n=Integer.parseInt(br.readLine());
		if(n<s[0]) {	// n이 s의 가장 작은 값 보다 작으면 나올 수 있는 경우의 수 
			ans+=(s[0]-n)*(n-1);	// 찾는 값과 뒤로 있는 수의 갯수를 구하고, 찾는 값보다 앞에 있는 값을 곱하면 
			ans+=s[0]-1-n;	// 검색 값 뒤로 있는 갯수를 찾아서 [n, n+1], [n, n+2], [n, n+m]이 될 수 있는 수를 찾음
		}
		// 5
		// 5 7 9 10 12
		// 3
		// 이 경우에 [1 2 3 4]를 이용하여 값을 찾을때 [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]로 답은 5가 나온다
		// [1, 3], [1, 4], [2, 3], [2, 4]는 찾는 값보다 작은 수로 시작하는 구간을 찾는다.
		// [3, 4]는 찾는 값을 기준으로 이후에 있는 갯수를 구해서 찾는다
		else {
			for(int i=1;i<l;i++) {
				if(s[i-1]< n && n<s[i]) {
					ans+=(s[i]-n)*(n-(s[i-1]+1));
					ans+=s[i]-1-n;
					break;
				}				
			}
		}
		System.out.println(ans);
	}
}