[BOJ] 24453 디버깅

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

24453번: 디버깅

문제

인규는 자동으로 코드를 생성해주는 프로그램을 이용해 코드를 작성하곤 한다.

하지만, AI는 완벽하지 않기 때문에 자동으로 생성된 코드에 오류가 있을 수도 있다.

따라서 인규는 코드를 자동으로 생성한 뒤, 코드를 한 줄씩 읽으면서 오류를 찾는 과정을 거친다.

인규가 쓰는 코드 에디터는 매우 똑똑해서 작성된 코드에서 오류가 없는 연속된 X$X$줄이 존재한다면, 특정 커맨드를 통해 나머지 오류를 자동으로 해결할 수 있다. 즉, 인규는 자동으로 생성된 코드를 전부 수정하지 않고도 프로그램을 완성할 수 있다.

다만, 인규는 코드 에디터에 의존하는 것을 싫어하기 때문에, 오류를 Y$Y$개 이상 찾아 해결한 뒤에만, 에디터의 오류 해결 기능을 이용하려 한다.

두 음이 아닌 정수 X, Y그리고 자동으로 생성된 코드에서 오류가 있는 줄 번호가 주어질 때, 에디터가 해결할 오류 개수의 최댓값을 구하는 프로그램을 작성하시오.

단, 한 줄에는 최대 한 개의 오류만 존재한다.

입력

첫 줄에는 자동으로 작성된 코드 줄의 수 N$N$과 오류가 있는 줄의 개수 M$M$이 주어진다. (1≤N≤2×10^7, 1≤M≤min(N,10^5))

두 번째 줄에는 코드에서 오류가 있는 줄의 번호 M$M$개가 공백으로 구분되어 주어진다.

다음 줄에는 정수 X, Y가 공백으로 구분되어 주어진다. (0≤X≤N, 0≤Y≤M)

출력

에디터가 해결할 오류 개수의 최댓값을 출력한다.

---

풀이

알고리즘은 다음과 같다.

1. 포인터 두개를 시작점으로 잡는다. ( start=1,end=1)
2. 만약 start 부터 end까지 조건을 만족하지 못한다면 end에 1을 더하고 그렇지 않다면 start에 1을 더한다
3. 두 조건을 만족한다면 ans를 start 부터 end까지 에러개수와 비교하여 최소값으로 갱신해준다.

조심해야 할 점은 N==1일 때, 예외 처리를 해줘야 한다는 것이다.

두 포인터를 사용하므로 시간복잡도 O(N)에 처리할 수 있다

자세한 내용은 코드에...

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

bool error[20000001];
int N,M;
int X,Y;

void input() {
    cin>>N>>M;
    int x;
    for(int i=0;i<M;i++){
        cin>>x;
        error[x]=true;
    }
    cin>>X>>Y;
}

void init() {
}


void solution() {
    int start=1,end=1;
    int er_cnt=0; // er_cnt는 start~end까지 에러의 개수
    int su_cnt=0; // su_cnt는 start~end까지 연속된 줄의 개수
    int ans=INT_MAX; // ans는 인규가 지워야하는 최소 에러 개수가 된다.
    
    if(N==1){
        cout<<M-Y; // N은 1일 때, (에러의 개수-인규가 찾아야하는 에러개수) 출력
        return;
    }
    
    while(1){
        if(start==N) break;
        if((er_cnt<Y||su_cnt<X)&&end<=N){ //모든 조건을 만족하지 않은 경우 end를 움직인다.
            if(error[end++]) er_cnt++; //현재 줄에 에러가 있다면 에러 개수를 늘려준다.
            su_cnt++;
        }else{
            if(er_cnt>=Y&&su_cnt>=X) ans=min(ans,er_cnt); //모든 조건을 만족한다면 ans를 갱신해준다.
            if(error[start++]) er_cnt--; //현재 줄에 에러가 있다면 에러 개수를 줄여준다.
            su_cnt--;
        }
    }
    
    //전체 에러의 개수 - 최소로 인규가 지워야하는 에러의 개수가 답이 된다.
    cout<<M-ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}