[백준] 1059번 : 좋은구간 [Java]

https://www.acmicpc.net/problem/1059

1059번: 좋은 구간

 

 

---

 

 

 

 

 

● 문제

[백준] 1059번

 

 

 

 

● 접근 방법

low 와 high 로 점점 좁혀가며 구해보자.

S집합은 오름차순으로 정렬하여 계산하기 쉽게 만들자.

 

예를 들어 S집합을 [1, 5, 9, 40, 100], n은 31로 정하자.

그런데 S[0]은 n보다 작다. 한마디로 중간값이 없을 수 밖에 없는 수.

 

그러므로 1은 버리고 low와 high 를 초기화 시켜주는 것이다.

그렇게 1,5 9 는 버려지게 되는 것이다.

 

이제 S[3] > n 보다 크다. 그럼 low는 S[2] + 1 부터 S[3] - 1 까지 즉 low는 9 + 1 = 10, high는 40-1 = 39 라는 것.

그럼 이제 이 구간의 총 개수를 구해야하는데 이것을 공식으로 작성하면

구간의 총 개수 = (high - n) + (n - low) * (high - n + 1) 이다.

 

그냥 저것을 클리어하면 될까? n과 S집합의 값이 같은 경우는? 당연하게도 좋은 수는 없게되는 것이다.

이정도만 예외처리를 해주면 된다.

 

 

 

 

● 문제 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) {
		
		int low = 0, high = 0;
		
		//입력
		Scanner sc = new Scanner(System.in);
		
		int l = sc.nextInt();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		
		for(int i = 0; i < l; i++) {
			arr.add(sc.nextInt());
		}
		
		int n = sc.nextInt();
		
		
		//풀이
		arr.sort((o1, o2) -> o1 - o2); // 오름차순 람다
		
		for(int i = 0; i < arr.size(); i++) {
			if(arr.get(i) > n) {
				if(i==0) low = 1;
				else low = arr.get(i-1) + 1;
				
				high = arr.get(i) - 1;
				break;
			} else if(arr.get(i) == n) {
				low = high = 0;
				break;
			}
		}
		
		int answer = (high - n) + (n - low) * (high - n + 1);
		
		//출력
		if(high == 0 && low == 0) System.out.println("0");
		else System.out.println(answer);
		
	}
}