[C++백준 1059:좋은 구간]

문제링크

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

1059번: 좋은 구간

 

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

제한

• 1 ≤ L ≤ 50
• 집합 S에는 중복되는 정수가 없다.
• 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
• 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

해석

집합에 포함된 정수들을 오름차순으로 정렬해주고 n이 들어갈 수 있는 구간을 찾는다.

구간은 (n보다 작은 수 + 1)부터 (n보다 큰 수 - 1) 까지이다.

이 때 n이 집합에 포함된 가장 작은 수보다 작을 경우도 고려해야 한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int good(vector<int> set, int n) {
    int i = 0, j = 0;
    int start = 0, end = 0;
    int set_size = set.size();
 
    // left, right를 찾고 범위를 만들기위해 left에는 +1을, right에는 -1을 해준다.
    for (i = 0; i < set_size; i++) {
        if (set[i] <= n && set[i+1] > n) {
            start = set[i] + 1;
            end = set[i + 1] - 1;
            break;
        }
    }
 
    // 입력받은 수보다 작은 n이 들어왔을 경우 start를 1로, end를 (첫째 항-1)로 설정
    if (start == 0 && end == 0) {
        start = 1;
        end = set[0] - 1;
    }
    
    // n이 입력한 수와 같다면 0리턴
    if (start == n+1)return 0;
 
    else return (n - start) * (end - n + 1) + (end - n);
}
 
int main() {
    int L, n, val;
    vector<int> set;
    cin >> L;
    for (int i = 0; i < L; i++) {
        cin >> val;
        set.push_back(val);
    }
    cin >> n;
 
    // 오름차순 정렬
    sort(set.begin(), set.end());
 
    cout << good(set, n) << '\n';
}

 

Memo

n이 집합의 가장 작은 수보다 작을 때를 고려하지 못해서 해결하기까지 꽤나 오랜시간이 걸렸다. 

다음에 다시 한번 더 풀어보도록 하자.