[백준 - S4] 1059. 좋은 구간

문제

정수 집합 S에서 n이 포함되는 좋은 구간 [A, B]의 개수를 구하기

좋은 구간 [A , B]란

• A <= x <= B 를 만족하는 모든 정수 구간

 

제출 코드 및 문제 풀이

1. n이 속하는 S에서의 구간을 구한다. => [left, right]

2. 이중 for문으로 left + 1에서 right - 1 까지의 모든 경우의 수를 구한다.

 

주의 할 점

1. 집합 S를 정렬해야 한다.
2. n은 최대 범위가 집합 S에서의 가장 큰 원소이지만, 최소 범위는 n >= 1이다.
   [5, 10, 15] 라면, 좋은 범위는 [1, 2], [1, 3], [1, 4] 가 된다.

 

public class Main {

    static int S;
    static int[] nums;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = Integer.parseInt(br.readLine());
        nums = new int[S];

        String[] split = br.readLine().split(" ");

        for (int i = 0; i < S; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }

        Arrays.sort(nums);

        int n = Integer.parseInt(br.readLine());
        int left = 0, right = 0;
        for (int i = 0; i < S - 1; i++) {
            if (n < nums[0]) {
                left = 0;
                right = nums[0];
                break;
            }

            if (nums[i] <= n && nums[i + 1] >= n) {
                left = nums[i];
                right = nums[i + 1];
                break;
            }
        }

        int ans = 0;
        for (int i = left + 1; i < right - 1; i++) {
            for (int j = i + 1; j < right; j++) {
                if (i <= n && n <= j) {
                    // System.out.println(i + " " + j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

 

 

링크

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