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

🔗 문제

---

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

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

입력

첫째 줄에 정수 $N$ ($1 \le N \le 200\,000$)과 $K$ ($1 \le K \le 100$)가 주어진다.

둘째 줄에는 ${a_1, a_2, ... a_n}$이 주어진다 ($1 \le a_i \le 100\,000$)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

예제 입력 1 
9 2
3 2 5 5 6 4 4 5 7

예제 출력 1 
7

예제 입력 2 
10 1
1 2 3 4 5 6 6 7 8 9

예제 출력 2 
6

노트

연속 부분 수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분 수열을 말한다.

$a = {3, 9, 7, 6, 5}$ 일 때 $9, 7, 6$는 연속 부분 수열이고 $3, 6, 5$는 그렇지 않다.

😒 내가 생각한 아이디어

---

👀 문제를 통해 이해해보기

---

인풋으로

9 2
3 2 5 5 6 4 4 5 7 

이 들어왔다고 생각해보자.
해당 예제에서는 길이가 9인 수열에서 같은 정수를 2개 이하로 포함한 최장 연속 부분 수열의 길이를 구해야 한다.

사실 이 문제를 투 포인터 알고리즘으로 풀어야 한다고(과제로 나와서) 이미 알고 있어서 그렇게 접근하였지만, 애초에 인풋 제한 값도 $N$ 이 $200,000$ 이하라서 O(N^2) 의 시간 복잡도로 풀면 시간 초과가 나온다.
따라서 시간 복잡도를 O(N)으로 줄인 투 포인터 알고리즘을 이용해야 한다.

• 투 포인터 알고리즘(Two-Pointer Algorithm)

---

연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘
head와 tail을 갖는 포인터를 하나의 배열에 배치해놓고, 문제에 따라 특정 조건을 만족 시키면, head와 tail값을 조정해가면서 구간을 전부 훑어주는 것이다.

어떤 숫자들의 리스트가 주어질 때, 
해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 
문제를 투 포인터 알고리즘으로 풀어보자.
1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트한다.
3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

⚒️ 뚝딱뚝딱 설계

---

정확한 이해를 위해 인풋으로 들어온 예제를 투 포인터 알고리즘으로 풀어보자.

** 반복 조건: tail 포인터가 모든 배열의 값을 다 돌았을 때 반복 멈춤 **
** 투 포인터 알고리즘의 대전제: head포인터가 가리키는 인덱스가 tail포인터가 가리키는 인덱스를 넘어갈 수는 없습니다. **
if(등장횟수가 K보다 커지면) {
    1. head 포인터에 있었던 값 등장 횟수 빼어주기
    2. head 포인터 증가(언제까지? 모든 등장횟수가 K번 이하일 때까지)
 }
 else {
 	1. tail 포인터 증가
    2. tail 포인터가 가리키는 값이 등장하는 횟수 증가 
 }

🖥️ 정답 코드

---

// 20922 겹치는 건 싫어
/*
  투 포인터 알고리즘으로 풀 수 있는 문제였습니다.
*/ 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int MAX = 100001;

int solve(int &N, int &K, vector<int> &a, int cnt[]){
  int s, e = 0; 
  int len = -987654321;
  while(s <= e && e < N){ // 투 포인터 알고리즘의 전제: [s는 e 포인터가 가리키는 인덱스값을 넘어갈 수 없음] && [e는 배열의 맨끝 인덱스 미만] 이어야 한다.
    if(cnt[a[e]] == K){ // 조건 미충족이 되는 순간
      //a[s]를 세어줬던 cnt배열 값을 감소시키고,
      // s의 포인터값을 하나 증가시킨다.
      cnt[a[s]]--;
      s++;
    }
    else {
      cnt[a[e]]++; //해당 값 증가시켜주고
      e++; // 오른쪽 포인터 증가
    }
    len = max(len, abs(s-e));
  }
  return len;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  int N, K;
  cin >> N >> K;
  vector<int> a(N, 0); // 수열
  int cnt[MAX] = {0, };
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }  
  cout << solve(N, K, a, cnt) << "\n";
}