[BaekJoon] 1059번 - 좋은 구간 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 집합에서 $x$ 를 포함하면서 $x$ 가 집합에는 포함되지 않는 좋은 구간의 개수를 구하는 문제로 이런 좋은 구간이 될 수 있는 구간 양 끝 값의 상한과 하한을 구해줬다. 주어진 집합을 순회하며 $x$ 보다 같거나 작은 수 중에서 가장 큰 수와 $x$ 보다 같거나 큰 수 중에서 가장 작은 수를 구하면 좋은 구간의 양 끝 상한과 하한을 구할 수 있다. 좋은 구간이 $x$ 도 포함해야 하므로 구간의 하한과 $x$ 사이에서 수 하나, 구간의 상한과 $x$ 사이에서 수 하나를 뽑으면 좋은 구간 하나를 만들 수 있고 두 경우의 수의 곱으로 전체 경우의 수를 구할 수 있다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int l = Integer.parseInt(br.readLine());

        int[] arr = new int[l];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < l; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int n = Integer.parseInt(br.readLine());

        int min = 0;
        int max = 1001;
        for (int x : arr) {
            if (x <= n) min = Math.max(min, x);
            if (x >= n) max = Math.min(max, x);
        }

        System.out.println(Math.max((n - min) * (max - n) - 1, 0));
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l;
    cin >> l;

    vector<int> v(l);
    for (int& x : v) cin >> x;

    int n;
    cin >> n;

    int mn = 0;
    int mx = 1001;
    for (int x : v) {
        if (x <= n) mn = max(mn, x);
        if (x >= n) mx = min(mx, x);
    }

    cout << max((n - mn) * (mx - n) - 1, 0);
}

---