#1059 : 좋은 구간

풀이방법

사용된 것:

정렬

수학

 

2022.06.12

먼저, 좋은 구간에 들어갈 수 있는 수들의 범위를 찾는다.

편의를 위해 이 범위에 속하는 수들의 집합을 T라고 하겠다.

 

T의 모습은 N의 값에 따라 다음의 셋 중 한 가지로 결정된다.

 

첫째,

N이 집합 S의 수들 중 하나와 값이 같을 경우, T에 들어갈 수 있는 수는 없다. 이 경우에는 정답이 0이므로 화면에 0을 출력하고 끝내면 된다.

 

둘째,

N이 집합 S의 수들 중 가장 작은 수보다 작을 경우, T에 들어갈 수 있는 수들의 범위는

1부터

(S의 가장 작은 수) - 1 까지

이다.

예를 들어 집합에 6, 9, 12가 있고 N이 2라면 T =  {1, 2, 3, 4, 5}이다.

 

셋째,

N이 집합 S의 어떠한 두 수 사이에 낀 수일 경우, T에 들어갈 수 있는 수들의 범위는

(집합 S의 수들 중 N보다 작은 수들 중 가장 큰 것) +1 부터

(집합 S의 수들 중 N보다 큰 수들 중 가장 작은 것) - 1 까지

이다.

예를 들어 집합에 2, 9, 15가 있고 N이 4라면 T = {3, 4, 5, 6, 7, 8}이다.

 

N이 S의 모든 수들보다 큰 경우는 없으므로 이렇게 세 가지 경우만 고려하면 된다.

 

 

이제 범위를 알았으니 좋은 구간의 개수를 구하면 끝이다.

 

 

 

좋은 구간은 세 가지가 있다.

이 세 가지 구간의 개수를 각각 모두 구한 뒤, 더하면 정답이 나온다.

 

첫째, N이 오른쪽 끝에 있는 구간.

이 경우에 속하는 좋은 구간의 개수는 정확히,

N - (집합 T에 속한 수 중 최솟값) 개이다.

 

둘째, N이 왼쪽 끝에 있는 구간.

이 경우에 속하는 좋은 구간의 개수는 정확히,

(집합 T에 속한 수 중 최댓값) - N 개이다.

 

셋째, N이 중간에 끼어 있는 구간.

이 경우에 속하는 좋은 구간의 개수는 정확히,

위의 첫째 구간의 개수와 둘째 구간의 개수를 곱한 값이다.

 

 

코드

Java(2022.06.12)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력값 읽어오기
		int l = Integer.parseInt(br.readLine());
		int[] arr = new int[l];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<l; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int n = Integer.parseInt(br.readLine());
		
		//풀이
		Arrays.sort(arr);	//S의 수들을 정렬
		
		int min = 1;	//집합 T의 최솟값
		int max = 0;	//집합 T의 최댓값
		for(int i:arr) {
			if(i==n) {System.out.print(0); System.exit(0);}	//N과 값이 같은 수가 S에 있을 경우
			
			if(i<n) min = i+1;
			else {max = i-1; break;}
		}
		//정답 계산 후 출력
		System.out.print(max-n + n-min + (max-n)*(n-min));

	}

}