1부터 limit까지의 정수 중 모든 관측 조건을 만족하면서 제외 목록에 없는 값의 개수를 구해요.
rules의 각 행은 [연산 종류, 기준값]이에요. 종류 0은 기준값보다 커야 한다는 조건, 종류 1은 기준값 이하여야 한다는 조건이에요. banned에 적힌 값은 사용할 수 없어요. 같은 제외값이 여러 번 나와도 그 값 하나만 제외해요.
int solution(int limit, vector<vector<int>> rules, vector<int> banned)의 세 빈칸을 채워 주세요. intersect는 모든 관측 조건의 교집합 크기, fits는 한 정수가 모든 조건과 처음 범위에 맞는지 계산해요.
매개변수와 반환값
limit는 11,000이에요. 조건 수와 제외값 수는 각각 0100이에요. 조건 행의 길이는 2, 종류는 0 또는 1, 기준값과 제외값은 0~limit+1이에요. 조건·제외값은 중복될 수 있고 순서는 임의예요. 조건끼리 모순될 수 있어요. 가능한 값이 없으면 0을 반환해요. 두 배열 모두 빈 값일 수 있어요.
예시
limit=10, rules=[[0,3],[1,8]], banned=[4,4,10] → 4: 범위는 4~8의 다섯 개예요. 4는 한 번만 빼고, 범위 밖인 10은 개수에 영향을 주지 않아요.limit=6, rules=[[0,2],[1,5]], banned=[3,5] → 1: 후보 3·4·5 중 4만 남아요.
자동 채점 입력·출력
첫 줄은 limit, 조건 수 N, 제외값 수 M이에요. 다음 N줄에 종류와 기준값, 다음 줄에 제외값 M개가 있어요. M=0이면 이 줄은 없어도 돼요. 남은 개수를 한 줄에 출력해요. main은 채점용이며 작성 대상은 세 빈칸이에요.
예시 입력
10 2 3
0 3
1 8
4 4 10
예상 결과
4
예시 입력
6 2 2
0 2
1 5
3 5
예상 결과
1
핵심 개념
binary-search-range: 포함·제외 경계를 교집합의 양 끝으로 바꿔요.function-design: 범위의 크기와 개별 후보 판정을 구분해요.basic-sort-search: 중복된 제외값을 하나로 정리해요.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int intersect(vector<vector<int>> rules, int low, int high) {
for (vector<int> rule : rules) {
int op = rule[0], value = rule[1];
if (op == 0) low = max(low, /*@blank1@*/);
if (op == 1) high = min(high, /*@blank2@*/);
}
return max(0, high - low + 1);
}
bool fits(int value, vector<vector<int>> rules, int limit) {
if (value < 1 || value > limit) return false;
for (vector<int> rule : rules) {
if (rule[0] == 0 && value <= rule[1]) return false;
if (rule[0] == 1 && value > rule[1]) return false;
}
return true;
}
int solution(int limit, vector<vector<int>> rules, vector<int> banned) {
int answer = intersect(rules, 1, limit);
sort(banned.begin(), banned.end());
banned.erase(unique(banned.begin(), banned.end()), banned.end());
for (int value : banned) {
if (/*@blank3@*/) --answer;
}
return answer;
}
int main() {
int limit, n, m;
cin >> limit >> n >> m;
vector<vector<int>> rules(n, vector<int>(2));
for (int i = 0; i < n; ++i) cin >> rules[i][0] >> rules[i][1];
vector<int> banned(m);
for (int i = 0; i < m; ++i) cin >> banned[i];
cout << solution(limit, rules, banned) << '\n';
}