1. 문제 설명

• 주어진 N 길이의 수열에서 같은 숫자가 K번 이하로만 나오도록 하는 가장 긴 부분 수열의 길이를 구하는 문제
  ⇒ 같은 값이 K번 이하로만 등장하도록 유지하면서 연속 구간을 최대로 늘리는 문제
• [제약 조건] 연속 조건 & 등장 횟수

// [input]
9 2 // N K
1 1 2 1 2 2 1 1 2 // 수열

2. 스크래치

0) 문제 풀이

• 문제 유형: 투 포인터
• 각 숫자의 등장 횟수를 관리해야 하므로 빈도수 배열 / 맵을 사용
• right 포인터로 구간을 확장하며 숫자 등장 횟수를 카운팅
• 어떤 숫자의 빈도가 K를 초과하면 left포인터를 이동시키면서 초과한 숫자를 줄임
• 구간 길이 갱신

3. 풀이

주요 알고리즘

• 슬라이딩 윈도우 (투 포인터) + 빈도 카운팅

문제 쪼개기

1. freq[x] 배열을 입력값 최대의 크기로 설정
2. left, right 포인터를 0에서 시작
3. right를 0 ~ N-1까지 1씩 늘리며 구간 확인 [left, right]
   • 숫자의 등장 횟수를 카운팅: freq[x]로 현재 구간에서 x가 몇 번 나왔는지 카운팅
   • K를 초과하면 left를 이동시키며 등장횟수를 -1
4. 조건을 만족하는 구간의 길이 갱신하기 (right - left + 1)
5. right가 끝까지 이동할 때까지 반복

4. 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		// [input]
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

		// [logic]
		// 입력값의 크기의 카운팅 배열 만들기
        int[] freq = new int[100001];
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < N; right++) {
            freq[arr[right]]++;
						
			// 겹치는 원소가 K개를 초과하면
            while (freq[arr[right]] > K) {
                freq[arr[left]]--;
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        System.out.println(maxLen);
    }
}

5. De-fault

freq[arr[right]]++;

while (freq[arr[right]] > K) {
    freq[arr[left]]--;
    left++;
}

• right를 하나씩 늘리면서 구간 [left, right] 안에 포함된 원소들의 등장 횟수를 freq에 기록한 후,
  어떤 값 x가 K을 초과하여 등장했을 때 로직을 처리하는 부분이 어려웠음.
• 처음에 직관적으로는 ‘K번 횟수를 넘긴 그 값이 있는 위치를 찾아서 그 원소가 K번 이하로 나와야 하는게 아닌가?’라는 생각이 들었음
• 왜 left를 오른쪽으로 한 칸씩 밀어야 하는가?
  연속 부분 수열을 유지하면서 조건을 만족시키는 유일한 축소 방법이기 때문
• 문제의 핵심은 연속 부분 수열(구간)만 허용하는 점임.
  right를 하나 늘렸을 때 freq[arr[right]] > K 이면 해당 구간은 조건을 위반한 상태가 됨.
• 연속 구간을 유지하면서 이 위반 상태를 없애는 방법은
  왼쪽 포인터 left를 오른쪽으로 밀면서, 하나씩 구간 밖으로 내보내는 것
• 중간에 있는 원소를 선택해 빼버리면 연속 부분 수열이 아니게 되기 때문에 오직 left ++를 통해서 구간을 줄일 수 있음
  왼쪽으로 계속 밀다 보면 언젠가는 K번의 등장 횟수를 초과한 원소와 같은 값 하나가 잘려나감
• 이 시점에 freq[arr[right]] 이 다시 K이하로 떨어지고 해당 구간은 조건을 반족하게 됨
  이 때 이 순간의 구간길이 right - left + 1 max 값 갱신

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂