백준 20922 - 겹치는 건 싫어

 

 

문제 설명

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 $100,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다.  이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 수가 주어질 때, K개 이하로 중복을 허용하는 가장 긴 부분 수열의 길이를 구하는 것이다.

 

해당 문제의 부분 수열은 연속적이어야 하기 때문에 deque를 사용하여 앞, 뒤를 붙이거나 제거하며 풀어나가면 된다.

예를 들면, $K = 2$인 상황이다.

초록 부분은 K개 이하로 숫자를 추가할 수 있어서 문제없이 진행된 부분 수열이다.

빨간 부분인 5를 넣을 상황에서, 5는 이미 2개이기 때문에 추가할 수 없다.

따라서, 해당 부분을 추가하기 위해서는 앞에 있는 5중 하나를 제거해야 한다.

그렇다면 가장 먼저 나오는 5를 제거해야 가장 긴 부분 수열을 구할 수 있다.

 

해당 과정을 진행하기 위해서는 deque안에 있는 수들의 개수를 체크해야 한다.

따라서, deque에 숫자를 추가하고 뺄 때, 숫자를 카운팅 하는 자료구조를 하나 두어야 한다.

처음에는 이를 map으로 진행하였다.

문제를 해결하기는 했지만, 시간이나 메모리가 많이 들었다.

 

이를 개선하기 위해, 문제에서 주어진 최대 크기의 vector를 만들어 카운팅 했더니 확연히 자원을 줄일 수 있었다.

 

정리하면, deque에 맨 뒤에 숫자를 추가하며 부분 수열을 만든다.

만약, 추가하려는 수가 deque안에 K개 이상 존재한다면 deque에 앞에서부터 숫자를 제거하는 작업을 K개 미만이 될 때까지 진행한다.

수를 추가했다면 현재 deque의 길이를 통해 가장 긴 부분 수열의 길이를 갱신하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, K;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;

    deque<int> dq;
    vector<int> window(200'001, 0);
    int ans = 0;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;

        while (!dq.empty() && window[num] >= K)
        {
            int front = dq.front();
            dq.pop_front();

            window[front]--;
        }

        dq.push_back(num);
        window[num]++;

        ans = max(ans, (int)dq.size());
    }

    cout << ans;

    return 0;
}

---