[BOJ] 2531 회전 초밥

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

코드 1 - 실패

문제를 초밥 먹는 개수를 최대로 하기로 잘못 이해했다.

n, d, k, c = map(int, input().split())

sushi = [int(input()) for _ in range(n)]


start = -1
dif = -1
ans = -1

ns = []
for i, v in enumerate(sushi):
  if v == c:
    ns = sushi[i:] + sushi[:i]
    break

for i, v in enumerate(ns):
  if v == c:
    if start != -1 and i - start >= k:
      print(i, start)
      ans = k + 1
    start = i
    
  if i == n-1 and start == 0:
    ans = k + 1
if ans == -1:
  print(k)
else:
  print(ans)

그냥 단순히 쿠폰의 위치를 찾고 쿠폰이 없는 구간 중 k개 이상인 구간을 찾아서 해결했는데 당연하게도 틀렸다.

코드 2 - 브루트포스

n, d, k, c = map(int, input().split())

sushi = [int(input()) for _ in range(n)]

eat = set()

ans = 0
for i in range(n):
  if i + k <= n:
    eat = set(sushi[i:i+k])
  else:
    eat = set(sushi[i:] + sushi[:(i+k)%n])
  
  eat.add(c)
  ans = max(ans, len(eat))
  
print(ans)

k개만큼 슬라이드 돌면서 set으로 중복 제거하고 마지막에 쿠폰으로 먹는거 하나 추가해서 그 개수를 구했다. 그리고 최대값과 비교했다.

코드 3 - 슬라이딩 윈도우

문제 유형 중 슬라이딩 윈도우가 있길래 해당 방법으로 풀어보았다.

from collections import defaultdict

n, d, k, c = map(int, input().split())

sushi = [int(input()) for _ in range(n)]

sushiType = defaultdict(int)
sushiType[c] += 1

sushi += sushi[:k-1]

for i in range(k):
  sushiType[sushi[i]] += 1
  

left = 0
right = k

ans = len(sushiType)
tmp = ans

while right < len(sushi):
  sushiType[sushi[right]] += 1
  sushiType[sushi[left]] -= 1

  if sushiType[sushi[right]] == 1:
    tmp += 1
  if sushiType[sushi[left]] == 0:
    tmp -= 1
    
  right += 1
  left += 1
    
  ans = max(ans, tmp)
  
print(ans)

스시의 타입을 저장할 딕셔너리를 만들고 스시의 타입 개수에
따라 먹게되는 스시의 종류를 구했는데 틀렸다.

GPT한테 물어보니까

from collections import defaultdict

n, d, k, c = map(int, input().split())

sushi = [int(input()) for _ in range(n)]

sushiType = defaultdict(int)
sushiType[c] += 1

sushi += sushi[:k-1]

for i in range(k):
  sushiType[sushi[i]] += 1
  

left = 0
right = k

ans = len(sushiType)
tmp = ans

while right < len(sushi):
  
  if sushiType[sushi[right]] == 0:
    tmp += 1
    
  sushiType[sushi[right]] += 1
  sushiType[sushi[left]] -= 1
  if sushiType[sushi[left]] == 0:
    tmp -= 1
    
  right += 1
  left += 1
    
  ans = max(ans, tmp)
  
print(ans)

이렇게 코드를 수정했다.

while right < len(sushi):
  sushiType[sushi[right]] += 1
  sushiType[sushi[left]] -= 1

  if sushiType[sushi[right]] == 1:
    tmp += 1
  if sushiType[sushi[left]] == 0:
    tmp -= 1
    
  right += 1
  left += 1
    
  ans = max(ans, tmp)

구체적으로 이 부분인데

while right < len(sushi):
  
  if sushiType[sushi[right]] == 0:
    tmp += 1
    
  sushiType[sushi[right]] += 1
  sushiType[sushi[left]] -= 1
  if sushiType[sushi[left]] == 0:
    tmp -= 1
    
  right += 1
  left += 1
    
  ans = max(ans, tmp)

sushi[sushi[right]]를 검사하는 부분을 선 더하기 후 검사에서 선 검사 후 더하기로 바뀌었다.

선 더하기 후 검사를 하면 같은 스시가 추가되고 삭제되는 경우 +- 1의 결과가 1일 때 가지수는 그대로지만 코드에서는 가지수가 1이 증가된 것으로 판단하게 된다.

조건에 따라 더하기, 빼기를 할 경우 그 상태에서 판별하고 값을 변경시키는 습관을 들여야겠다.