문제
접근
투 포인터 문제이다.
start, end 두 개의 변수를 이용하여 배열을 한 바퀴 돌면 된다.
start ~ end 사이에 있는 초밥을 먹는다고 생각하면 된다.
start가 0부터 시작해서 n-1까지 돌면 모든 경우의 수를 확인한 것이다.
안겹치는 초밥을 카운팅할 때 바로바로 확인하기 위해서 인덱스를 이용한 헤시맵을 이용했다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys
input = sys.stdin.readline
def twoPointer(arr, n, d, k, c):
start = 0
end = 0
hashmap = [0] * 5000
hashmap[arr[start]] += 1
hashmap[c] += 1
cnt = 1
if arr[start] != c:
cnt += 1
ans = 0
while True:
end = (end + 1) % n
hashmap[arr[end]] += 1
if hashmap[arr[end]] == 1:
cnt += 1
if (end - start + n) % n == k:
hashmap[arr[start]] -= 1
if hashmap[arr[start]] == 0:
cnt -= 1
start = (start + 1) % n
if ans < cnt:
ans = cnt
if start == n-1:
break
return ans
def main():
n, d, k, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
if n == k:
ansList = set(arr)
ansList.add(c)
print(len(ansList))
else:
print(twoPointer(arr, n, d, k, c))
if __name__ == "__main__":
main()