백준 20922번 겹치는 건 싫어 문제 풀이

문제 설명

• 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
• 100,000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

문제를 보고 든 생각

• 투 포인터 lp, rp를 만들고 공통인 숫자가 K번 초과로 나오면 lp를 증가시키고 아니면 rp를 증가시키면 되겠다.

풀이 간단 설명

1. map에 해당 숫자가 몇 번 나오는지 저장했다.
2. K번 초과로 나오면 lp에 해당하는 나온 숫자를 하나씩 줄이고 lp를 하나씩 증가시켰다.
3. 아니면 rp를 오른쪽으로 하나씩 이동했다.

코드

#include <iostream>
#include <vector>
#include <map>

#define MAX_N 200000

using namespace std;

int N, K;
vector<int> v;
map<int, int> m;
int longest;

void getInput(){
  cin >> N >> K;
  for(int i=0; i<N; ++i){
    int temp; cin >> temp;
    v.push_back(temp);
  }
}

void getLongest(){
  int lp = 0;
  int rp = 0;

  int arrLen = 0;
  while(rp < N){

    if(m[v[rp]] + 1 > K){
      m[v[lp++]] -= 1;
      --arrLen;
      continue;
    }
    ++m[v[rp++]];
    ++arrLen;
    if(arrLen > longest){
      longest = arrLen;
    }
  }
}

void solve(){
  getInput();
  getLongest();
  cout << longest;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}