[백준 20922] - 겹치는 건 싫어(C++)[실버1]

 

🔎문제 해석

N의 크기가 최대 200,000이므로, O(N^2)인 알고리즘은 사용하면 안 된다.
따라서 모든 수열의 경우의 수를 탐색해야 하는 이 문제는 투 포인터 알고리즘을 사용해서 O(N) 알고리즘으로 풀어야 합니다.

 

우선 다른 투 포인터 알고리즘 문제와 동일하게 start, end를 사용합니다.

우선 start와 end를 0으로 초기화해줍니다.

그다음 숫자가 해당 부분수열에서 몇 번 포함되었는지를 기록하는 배열도 필요합니다.

N의 최대크기는 200,000이고, N의 최댓값은 100,000이므로 배열의 최대 크기는 100,001이 될 것입니다. V [100001];

 

end가 n이 되기 전까지 해당 과정을 반복합니다.

1. end가 가리키는 원소가 등장하는 횟수를 비교해 줍니다.
   1. k개 이하라면, 등장하는 횟수를 증가시켜 주고, end를 한 칸 증가시켜 줍니다.
   2. k개 초과라면, start 포인트가 가리키는 원소의 등장하는 횟수를 감소시켜 주고, start를 한 칸 증가시켜 줍니다.
2. 길이의 최댓값은 매 과정마다 갱신해 줍니다.

 

이제 그림으로 설명해 드리겠습니다.

 

⬇️(start)⬇️(end) 

3

2

5

5

6

4

4

5

7

초기에는 start와 end가 동일한 지점을 가리킵니다.

3이 등장하는 횟수는 0번이기에, 3이 등장하는 횟수를 1번으로 증가시켜 주고, end 포인트를 한 칸 증가시켜 줍니다.

 

⬇️(start)          ⬇️(end)

3

2

5

5

6

4

4

5

7

2가 등장하는 횟수는 0번이기에, 2가 등장하는 횟수를 1번으로 증가시켜 주고, end 포인트를 한칸 증가시켜 줍니다.

 

⬇️(start)                                 ⬇️(end)

3

2

5

5

6

4

4

5

7

5가 등장하는 횟수는 0번이기에, 5가 등장하는 횟수를 1번으로 증가시켜주고, end 포인트를 한칸 증가시켜 줍니다.

 

⬇️(start)                                                             ⬇️(end)

3

2

5

5

6

4

4

5

7

5가 등장하는 횟수는 1번이기에, 5가 등장하는 횟수를 2번으로 증가시켜주고, end 포인트를 한 칸 증가시켜 줍니다.

 

⬇️(start)                                                                                      ⬇️(end)

3

2

5

5

6

4

4

5

7

6이 등장하는 횟수는 0번이기에, 6이 등장하는 횟수를 1번으로 증가시켜주고, end 포인트를 한 칸 증가시켜 줍니다.

 

⬇️(start)                                                                                                                      ⬇️(end)

3

2

5

5

6

4

4

5

7

4가 등장하는 횟수는 0번이기에, 4가 등장하는 횟수를 1번으로 증가시켜주고, end 포인트를 한 칸 증가시켜 줍니다.

 

⬇️(start)                                                                                                                                ⬇️(end)

3

2

5

5

6

4

4

5

7

4가 등장하는 횟수는 1번이기에, 4가 등장하는 횟수를 2번으로 증가시켜주고, end 포인트를 한 칸 증가시켜 줍니다.

 

⬇️(start)                                                                                                                                                                                 ⬇️(end)

3

2

5

5

6

4

4

5

7

5가 등장하는 횟수는 2번이기에, 이번에 포함하면 k개 초과되는 상황이 발생합니다. 

따라서 start 포인트를 한 칸 증가시켜주고, start가 가리키는 원소인 3의 등장 횟수를 -1해 줍니다.

 

                        ⬇️(start)                                                                                                                                                         ⬇️(end)

3

2

5

5

6

4

4

5

7

위 상황을 보면 5에 등장 횟수는 계속 고정이기에, 5를 만나기 전까지 start는 계속 증가될 것입니다.

 

이런 식으로 end가 모든 원소를 탐색한다면 탐색을 종료하고, 그때의 최장 길이를 반환해 주면 됩니다.

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n,k;
vector<int>ary;
vector<int>v;
int main(){
    cin>>n>>k;
    ary.resize(n,0);
    v.resize(100001,0);
    for(int i=0; i<n;i++){
        cin>>ary[i];
    }
    int start=0, end=0,result=0;
    while(end<n){
        if(v[ary[end]]==k){ //방문한 원소가 k개 초과일경우
            v[ary[start]]--;
            start++;
        }
        else{
            v[ary[end]]++;
            end++;
        }
        result=max(result,end-start);
    }
    cout<<result<<endl;
}

 

😀느낀 점

• 투 포인터 알고리즘을 계속 풀다 보니 감이 잡히는 것 같다.
• 모든 경우의 수를 탐색하고 싶은데 시간초과 때문에 불가능하다면 이제 투 포인터 알고리즘을 사용해야겠다.