[Silver 1] 20922 겹치는 건 싫어

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

20922번: 겹치는 건 싫어

 

이 문제는 투 포인터를 통해 해결할 수 있다.

K의 값에 따라 연속 수열에 들어올 수 있는 같은 값의 개수가 달라진다.

 

예시에 있는 3 2 5 5 6 4 4 5 7은 K가 2이므로 수열에 같은 값이 2개 이하 존재해야한다.

즉, 3 2 5 5 6 4 4와 2 5 5 6 4 4, 5 5 6 4 4, 5 6 4 4 5 7, 6 4 4 5 7, ... 이 가능하다.

이중 가장 긴 수열의 길이는 7이므로 답은 7이 된다.

 

이 문제를 해결하기 위해 그림을 그려보면 아래와 같다.

 

step 1 (초기화)

element 배열

1	2	3	4	5	6	7
0	0	0	0	0	0	0

arr 배열

3(end)(start)

2

5

5

6

4

4

5

7

result = 0

 

step 2 

element 배열

1	2	3	4	5	6	7
0	0	1	0	0	0	0

arr 배열

3 (end)

2 (start)

5

5

6

4

4

5

7

result = 1

 

step 2

element 배열

1	2	3	4	5	6	7
0	1	1	0	0	0	0

arr 배열

3 (end)

2

5 (start)

5

6

4

4

5

7

result = 2

 

step 3

element 배열

1	2	3	4	5	6	7
0	1	1	0	1	0	0

arr 배열

3 (end)

2

5

5 (start)

6

4

4

5

7

result = 3

 

step 4

element 배열

1	2	3	4	5	6	7
0	1	1	0	2	0	0

arr 배열

3 (end)

2

5

5

6 (start)

4

4

5

7

result = 4

 

step 5

element 배열

1	2	3	4	5	6	7
0	1	1	0	2	1	0

arr 배열

3 (end)

2

5

5

6

4 (start)

4

5

7

result = 5

 

step 6

element 배열

1	2	3	4	5	6	7
0	1	1	1	2	1	0

arr 배열

3 (end)

2

5

5

6

4

4 (start)

5

7

result = 6

 

step 7

element 배열

1	2	3	4	5	6	7
0	1	1	2	2	1	0

arr 배열

3 (end)

2

5

5

6

4

4

5 (start)

7

result = 7

 

step 8

element 배열

1	2	3	4	5	6	7
0	1	0	2	2	1	0

arr 배열

3

2 (end)

5

5

6

4

4

5 (start)

7

result = 7

 

step 9

element 배열

1	2	3	4	5	6	7
0	0	0	2	2	1	0

arr 배열

3

2

5 (end)

5

6

4

4

5 (start)

7

result = 7

 

step 10

element 배열

1	2	3	4	5	6	7
0	0	0	2	1	1	0

arr 배열

3

2

5

5 (end)

6

4

4

5 (start)

7

result = 7

 

step 11

element 배열

1	2	3	4	5	6	7
0	0	0	2	2	1	0

arr 배열

3

2

5

5 (end)

6

4

4

5

7 (start)

result = 7

 

step 12

element 배열

1	2	3	4	5	6	7
0	0	0	2	2	1	1

arr 배열

3

2

5

5 (end)

6

4

4

5

7

result = 7

 

위 과정을 코드로 변환하면 아래와 같다.

#include<iostream>

using namespace std;

int N, K;
int arr[200001];
int element[100001];
int result = 0;

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int start = 0;
	int end = 0;
	
	while (start < N) {
		if (element[arr[start]] != K) {
			element[arr[start]]++;
			start++;
		}
		else {
			element[arr[end]]--;
			end++;
		}
		result = max(result, start - end);
	}

	cout << result << '\n';
	return 0;
}