[알고리즘/백준] 20922: 겹치는 건 싫어

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

1. 문제 접근

주어진 수열 안에서 같은 원소가 K개 이하로 들어있는 부분 수열의 길이를 구하는 문제이다.

정수의 최댓값을 크기로하는 배열을 만들고 0으로 초기화 한다. 이후 숫자에 해당하는 인덱스에 접근하여 원소의 개수를 체크할 수 있다.

 

투 포인터를 활용하여 O(N)의 시간복잡도에서 해결한다.

 

left 와 right 를 0으로 초기화한 뒤,

right의 원소가 K개 이하면 right를 1 증가시키고

right의 원소가 K개를 초과한다면 left를 1 증가시키며

right 가 N 이상이라면 반복문을 빠져나온다.

 

2. 코드

#include <iostream>
#include <vector>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    const int MAX = 100000;

    int N, M;
    std::cin >> N >> M;
    std::vector<int> vec(N),check(MAX+1);

    for (int i = 0; i < N; ++i)
    {
        std::cin >> vec[i];
    }

    int left = 0;
    int right = 0;
    int maxValue = 0;

    while (true)
    {
        if (right >= N)
        {
            maxValue = std::max(maxValue, right-left);
            break;
        }

        if (check[vec[right]] < M)
        {
            ++check[vec[right]];
            ++right;
        }
        else
        {
            --check[vec[left]];
            maxValue = std::max(maxValue, right - left);
            ++left;
        }
    }
    std::cout << maxValue;
    
}