[백준/C++] 알고리즘 20922번 - 겹치는 건 싫어

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 20922번 - 겹치는 건 싫어를 풀어보도록 하겠습니다.

 

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

20922번: 겹치는 건 싫어

 

[문제 접근]

N이 최대 20만이고, 시간 제한이 1초이기 때문에 O(N^2)은 불가능합니다.

이러한 상황과, 문제가 연속과 관련된 문제이기 때문에 투 포인터를 생각했습니다.

st와 en을 두어서 중복개수 조건에 따라 st와 en이 변칙적으로 함께 움직이는 방법을 생각했는데 

최장길이를 어떻게 찾을지 그림이 그려지지 않았습니다. 그래서 st를 for문으로 고정했고, 중복 개수 조건에따라 en만

움직이도록 하는 방법을 생각했습니다.

 

[풀이 전략]

1. st를 for문으로 한 칸씩 확인하도록(고정) 합니다.

2. en을 0으로 초기화합니다.

3. 각 원소의 중복개수를 세고 en을 증가시킵니다.

4. 만약 en이 n이거나 en이 가리키는 원소의 중복개수가 k개라면 while문을 멈춥니다.

5. en-st로 길이를 구하고, 최장 길이를 담고 있는 변수와 비교하여 더 크면 업데이트합니다.

6. for문의 한 턴이 끝나기 전에 st가 가리키는 원소의 중복개수를 감소시킵니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;


// 겹치는 건 싫어.
int n, k ; // 수열의 길이, 중복 최대 개수.

int arr[200'001]; // 수열
int vis[100'001]; // 중복여부 판별.
int result ;

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> k ;

    for(int i = 0 ; i < n ; i++) cin >> arr[i];

    int en = 0 ;
    for(int st = 0 ; st < n-1 ; st++){
       
        while(en < n) {
        if(vis[arr[en]] == k) break;
            vis[arr[en]]++ ;
            en++;
        }
        result = max(result,en - st);
        vis[arr[st]]--;
    }
    cout << result ; 
}

 

[배울 점]

- 투 포인터라고 무작정 st,en잡고 움직일 생각말고, st나 en 중 하나는 for문을 사용하여 뼈대를 잡는 방법도 염두하기