[C#] 백준 20922 겹치는 건 싫어

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

 

문제 접근

투 포인터 문제로 연속되는 수열 중 같은 수가 k개 만큼 들어간다면 시작점 포인터를 같은 수의 앞까지 당기고 다시 같은 수가 나올 때 까지 연속되는 수열을 세는 방식으로 접근하였다.

 

Dictionary로 key값을 수열로 한 다음, 같은 수가 나올 때 마다 수를 증가시켜 k개보다 수가 커졌을 때 Dictionary의 key값을 통해 걸린 수 앞부분까지 0으로 만들어 준 후, 다시 세는 방식을 취했다.

 

풀이

 

using System;

class Program
{
    static void Main(string[] args)
    {
        string[] arrays = Console.ReadLine().Split();

        int n = int.Parse(arrays[0]);
        int k = int.Parse(arrays[1]);

        int[] a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
      
        Dictionary<int, int> dic = new Dictionary<int, int>();
        int maxLength = 0;
        int start = 0;

        for(int i = 0; i < n; i++)
        {
            int num = a[i];

            if (dic.ContainsKey(num))
                dic[num]++;
            else
                dic[num] = 1;

            while (dic[num] > k)
            {
                int startNum = a[start];
                dic[startNum]--;
                start++;
            }

            maxLength = Math.Max(maxLength, i - start + 1);
        }

        Console.WriteLine(maxLength);
    }
}

 

Dictionray 의 key값을 Array로 잡아두고, 해당 key값이 포함되어있는지 아닌지를 체크하여 포함되면 증가시키는 식으로 하였다.

 

그렇다면 수열에 같은 수가 나올 경우 수치가 증가하며, 그렇게 k보다 크게 되면 그만큼의 수열이 반복되었다는 뜻이다.

 

여기서 시작 포인터를 앞으로 당겨줘야 하는데, start 지점이 0인 상태에서 앞의 key값의 value를 0으로 만들면서 더 이상 세지않게 만들고, start의 수를 늘리면서 포인터를 앞으로 당겨준다.

 

그리고 끝지점 i - start + 1를 하면 해당 반복되는 구간의 크기를 알 수 있다. 배열의 인덱스가 0부터 시작하기 때문에 +1을 해줘야 정확한 크기가 나오게 된다.

 

maxLength를 반복하면서 계속 갱신해주고, k보다 큰 경우에 걸릴 경우 start를 늘림으로써 start 포인터 지점부터 끝부분까지의 크기와 현재 maxLength를 비교할 수 있게 된다.