백준 20922 - 겹치는 건 싫어 (C++)

 

 

주어진 수열의 부분 수열 중 같은 원소의 개수가 k개 이하인 수열중 가장 긴 수열을 구하면 된다.

 

예를 들어, 1223334444 라는 수열이 있다고 해보자.

이 수열에는 12233, 223334, 33344 등 여러 부분 수열이 존재한다.

 

각 부분 수열을 보면, 동일한 원소가 여러개 포함되어 있기도 한다.

12233의 경우엔 2와 3을 각각 2개씩 포함하고 있으며, 33344는 3을 3개, 4를 2개 포함하고 있다.

 

한 부분 수열에서 동일한 원소를 포함하고 있는 개수가 k개를 넘지 않는 건에서 가장 긴 수열을 구하면 된다.

 

주어진 수열은 1223334444이고, k는 2이라고 해보자.

12233 이라는 부분 수열은 총 5개의 길이를 지니고 있으며, 2는 2개, 3은 2개 가지고 있으므로 중복 원소의 개수가 k를 넘지 않는다.

 

하지만, 122333이 된다면, 3의 개수가 3개가 되어버리므로 k를 초과하는 부분 수열이 된다. 즉, 122333은 답이 될 수 없는 것이다. 

 

이런 조건을 고려하였을 때, 가장 긴 부분 수열의 길이를 출력하면 된다.

 

문제 풀이

 

투 포인터를 사용하면, 어렵지 않게 해결할 수 있다.

두개의 포인터를 사용하여, 수열을 하나씩 탐색하며, 중복 숫자의 개수가 k개가 넘지 않도록 관리하며 탐색해주었다.

 

입력은 1223334444 수열과, k는 2라고 가정해보자.

 

먼저 위의 배열은 투포인터가 가리키고 있는 범위 내에 숫자가 몇개 있는지를 기록하는 배열이다.

현재, 두 포인터 모두 0번 인덱스를 가리키고 있고, 1이 1개 포함되어 있으므로 1을 기록해주었다.

이제, R을 움직이며 탐색해보자.

 

R이 움직이면서 2가 범위에 포함되었으므로 2의 값도 1로 올려주었다.

 

다음 역시, R이 움직이면서 2를 2개 포함하게 되었으므로 2의 값을 2로 갱신해주었다.

조금 스킵해보겠다.

R이 이 구간까지 간다면, 수의 개수를 담은 배열은 위처럼 갱신되어있을 것이다.

이 때, 다음에서 문제가 발생한다.

3의 개수가 k를 초과하게 되어버린다.

즉, R이 이동하기 전의 L과 R의 범위가 중복 원소가 2인 부분 수열 중 하나의 경우가 된다는 것이다

그러므로, 이 때 길이를 기록해두고, L을 움직여서 다음 탐색 범위를 찾아야 한다.

현재 기록된 부분 수열의 최대 길이는 5가 될 것이다.

 

현재, 3이 3개이므로 3이 k개 이하가 될 때까지 L을 움직여보자.

 

이렇게 이동할 수 있다.

이전과 동일하게 R을 움직이며 구간을 탐색하면 된다.

 

끝까지 탐색해보면, 12233의 구간이 가장 긴 부분 수열이 될 수 있음을 알 수 있다.

 

풀이 코드

std::vector<int> NumCount(100001, 0);

int NumSize = 0;
int SameCount = 0;

std::cin >> NumSize >> SameCount;

std::vector<int> Sequence(NumSize);
for (int i = 0; i < NumSize; i++)
{
    std::cin >> Sequence[i];
}

 

먼저,  NumCount라는 배열을 선언해주었다.

현재 투 포인터가 가리키는 구간에 숫자가 몇개있는지 기록하는 배열이다.

수열에 어떤 숫자가 포함되어 있을 지 예상할 수 없으므로, 최대 범위인 100000에 맞게 resize해주었다.

 

int Left = 0;
int Right = 0;

int MaxLength = 0;

 

이후, 범위 양 끝을 가리킬 두 개의 포인터를 선언하였고, 조건에 맞는 부분 수열의 최대 길이를 저장할 MaxLength변수도 선언하였다.

 

while (Right < NumSize)
{
    int CurNum = Sequence[Right];
    NumCount[CurNum]++;

    if (NumCount[CurNum] > SameCount)
    {
        MaxLength = std::max(MaxLength, Right - Left);

        while (NumCount[CurNum] > SameCount)
        {
            int Num = Sequence[Left];
            NumCount[Num]--;
            Left++;
        }
    }

    Right++;
}

 

반복문을 돌며 위에서 설명한 것과 동일하게 진행하였다.

 

현재 Right가 가리키는 수의 NumCount를 증가시켜주었고, 만약 NumCount가 k보다 크다면, 이전 Right의 위치를 기준으로 부분 수열의 길이를 MaxLength에 갱신한 뒤, Right가 가리키는 숫자의 NumCount가 k이하가 될 때 까지 Left를 우측으로 당겨주었다. 

 

MaxLength = std::max(MaxLength, NumSize - Left);

std::cout << MaxLength;
return 0;

 

반복문이 끝난 후, 마지막 범위는 기록되지 않았으므로 MaxLength를 (NumSize - Left) 와 비교해서 더 큰 값으로 한 번 더 갱신해주었다.

 

마지막으로 MaxLength를 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();
    std::vector<int> NumCount(100001, 0);

    int NumSize = 0;
    int SameCount = 0;

    std::cin >> NumSize >> SameCount;

    std::vector<int> Sequence(NumSize);
    for (int i = 0; i < NumSize; i++)
    {
        std::cin >> Sequence[i];
    }

    int Left = 0;
    int Right = 0;

    int MaxLength = 0;

    while (Right < NumSize)
    {
        int CurNum = Sequence[Right];
        NumCount[CurNum]++;

        if (NumCount[CurNum] > SameCount)
        {
            MaxLength = std::max(MaxLength, Right - Left);

            while (NumCount[CurNum] > SameCount)
            {
                int Num = Sequence[Left];
                NumCount[Num]--;
                Left++;
            }
        }

        Right++;
    }

    MaxLength = std::max(MaxLength, NumSize - Left);

    std::cout << MaxLength;
    return 0;
}