방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 N의 범위가 30,000 이므로 투 포인터를 이용해서 풀어야 합니다. 초기 조건을 설정해 주고 해당하는 count배열에서 확인하면서 숫자가 있는지 없는지 확인하며 temp의 수를 구한 뒤 max(ans, temp)를 이용해서 풀어줍니다. 또한 회전 초밥 이므로 입력받은 배열을 2배로 늘려서 손쉽게 회전 초밥을 구현할 수 있습니다.

소스코드

n, d, k, c = map(int, input().split())
arr = []
ans = 0
count = [0] * 3001

for _ in range(n):
  arr.append(int(input()))

for i in range(n):
  arr.append(arr[i])

# 초기조건
for i in range(k):
  count[arr[i]] += 1
count[c] += 1
for i in range(3001):
  if count[i] != 0:
    ans += 1
count[c] -= 1

for i in range(k, n+k):
  count[arr[i-k]] -= 1
  count[arr[i]] += 1
  count[c] += 1
  temp = 0
  for j in range(3001):
    if count[j] != 0:
      temp += 1
  ans = max(ans, temp)
  count[c] -= 1
  
print(ans)