[백준, 자바, 1059번] 좋은 구간

풀이

• 처음에는 해당 문제에 대한 이해가 되질 않았다...
• 역시 알고리즘은 계속 풀면서 문제 이해하는 능력을 키워야하는 것 같다...
• 무튼 해당 문제에선 주어지는 집합 S에 해당하는 구간에 n을 포함하는 좋은 구간의 개수를 구하는 것으로
• S = [4,8,13,24,30], n = 10 의 경우엔 
• 8과 13 사이에 10이 속하기에 해당 구간에서 8과 13이 포함되지 않은
• 9와 12 사이에서 찾는것인데
• 처음엔 여기서 막혔다. 
  • 이유는 그러면 [ [9,10], [9,11], [9,12], [10,11],  [10,12], [11,12]] 이렇게 되는거 아닌가?
  • 그러다 문제에서 n을 포함하는 좋은 구간의 개수를 구해보자. 라는 말을 확인하게 되어 이해할 수 있었다.
• 이후 나머지는 간단한 연산 문제이기에 쉽게 해결되었지만 간과한 것이 
• 집합 S의 첫 번째의 것에 대한 조사도 해야하기에 S에 0을 추가하여 조사할 수 있도록 해결.
• 물론 정렬도 해줘야 함.

 

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

public class 좋은구간 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int L = Integer.parseInt(br.readLine());
        ArrayList<Integer> li = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i <= L; i++) {
            if (i == 0) li.add(0);
            else {
                li.add(Integer.parseInt(st.nextToken()));
            }
        }
        Collections.sort(li);
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < L; i++) {
            if (li.get(i) == n || li.get(i+1) == n) {
                System.out.println(0);
                break;
            } else if (li.get(i) <= n && n <= li.get(i+1)) {
                System.out.println((n-li.get(i)) * (li.get(i+1)-n) -1);
                break;
            }
        }
    }
}