1059번
정수집합 S가 주어졌을 때 좋은 구간을 count하는 문제이다.
좋은 구간이란, n은 포함하나, S의 어느 원소도 포함하면 안되는 구간이다.
전체적인 알고리즘은 다음과 같다.
정수집합 S를 정렬한다.
S에서 n보다 큰 수가 나올 때 까지 index를 증가시킨다. (구간의 기준점을 정해주기 위함이다)
S[index - 1] + 1 ~ S[index] - 1 까지의 모든 경우의 수 중에서
n을 포함하는 구간을 찾으면 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int check(int A, int B, int n)
{
if (A <= n && n <= B)
return (1);
return (0);
}
int main(void)
{
int L, n;
vector<int> S;
cin >> L;
int temp;
for (int i = 0; i < L; i++)
{
cin >> temp;
S.push_back(temp);
}
// 오름차순 정렬
sort(S.begin(), S.end());
cin >> n;
// 어느 구간을 체크할지 확인하기 위해 index를 증가시켜줌
int index = 0;
while (S[index] < n)
index++;
// S[index - 1] + 1이 시작점, S[index] - 1가 끝점이다.
int start, end;
start = S[index - 1] + 1;
end = S[index] - 1;
int count = 0;
// i 와 j는 시작점과 끝점의 모든 경우의 수를 접근하고,
// check함수를 통해 좋은구간인지 확인한다.
// i < j 이므로 i+1을 해 주었다.
for (int i = start; i <= end - 1; i++)
for (int j = i + 1; j <= end; j++)
if (check(i, j, n))
count++;
cout << count;
}