백준 15961번 회전초밥 풀러 가기

• 손님은 K개의 접시를 연속으로 먹는다
• 쿠폰에 적힌 C번 초밥을 무료로 먹을 수 있다

이 때 손님이 먹을 수 있는 초밥의 가짓수의 최댓값은?

구현 아이디어

1. K개의 초밥을 리스트에 담자
2. set(집합) 자료 구조를 사용하여 초밥의 가짓수를 계산하자
3. 쿠폰 초밥을 먹었을 때 초밥의 가짓수를 갱신하자
   • 이미 같은 번호 초밥을 먹었으면 가짓수는 그대로
   • 아직 안 먹었으면 가짓수가 1 증가
4. max 연산으로 초밥의 가짓수의 최댓값을 갱신하자

1트 - 시간 초과

import sys

input = sys.stdin.readline

# 접시의 수, 초밥의 가짓수, 연속해서 먹는 접시의 수, 쿠폰 번호
n, d, k, c = map(int, input().split())

# 벨트 위 초밥을 입력 받을 리스트
dish = []
for _ in range(n):
    dish.append(int(input()))

# 원형 리스트는 리스트 두 개를 합쳐 쉽게 인덱스 접근 가능
dish += dish

sushi = 0 # 손님이 먹은 초밥의 가짓수
ans = 1 # 손님이 먹을 수 있는 초밥의 가짓수의 최댓값

for i in range(0, n):
	# 연속하여 먹은 K개의 초밥을 temp 배열에 저장
    temp = dish[i:i+k]
	
    # 초밥의 가짓수를 계산
    sushi = len(set(temp))

    # temp에 쿠폰 초밥(c)가 있으면 가짓수의 최댓값은 증가하지 않음
    # temp에 c가 없을 때만 가짓수를 1 증가
    if c not in temp:
            sushi += 1
	
    # 초밥의 가짓수의 최댓값을 계산
    ans = max(ans, sushi)

print(ans)

문제의 입력 범위 제한을 다시 보자.

Worst Case일 때의 연산 횟수는
300만 x (3000 + 3000 + 3000 ) = 300만 x 9000 = 270억 번이 나와 1초 안에 해결하지 못한다.
( index slicing이나 in 연산 막 썼었는데 ... 앞으로 조심해야겠다고 느꼈다 )

2트 - 맞았습니다

슬라이딩 윈도우나 투 포인터의 핵심은 겹치는 부분을 계산하지 않고, 삭제된 부분과 추가된 부분만 계산해서 연산 횟수를 줄이는 것이다.
하지만 위 코드는 그렇게 동작하고 있지 않다!

최대 가짓수를 계산하기 위해서는 먹은 초밥(temp)에 앞으로 먹을 초밥이 들어있는지 확인해야 하는데 ... in 연산 없이 구현하는 방법이 떠오르지 않아 결국 다른 사람의 풀이를 보았다 🥹

구현 아이디어

• 투 포인터 알고리즘을 사용한다
  • 연속해서 먹는 접시의 수 k가 주어졌기 때문에 슬라이딩 윈도우도 가능하지만, 코드를 간단하게 하기 위해 포인터 변수를 2개 사용한 것 같다
• 🌟 초밥 번호를 key, 먹은 횟수를 value로 해서 key의 갯수를 센다 🌟
• defaultdict 클래스를 활용한다
  • defaultdict는 없는 key에 접근 or 조작하려고 할 때 key를 만들고 default 값을 자체적으로 생성
  • 기존 dictionary의 keyError를 보완

import sys
from collections import defaultdict

input = sys.stdin.readline

# 접시의 수, 초밥의 가짓수, 연속해서 먹는 접시의 수, 쿠폰 번호
n, d, k, c = map(int, input().split())

sushi = []
left = 0
right = 0
ans = 0

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

sushi += sushi

# int로 설정할 경우 default 값이 0
belt = defaultdict(int)

# 보너스 초밥은 먹고 시작
belt[c] += 1

# 첫 K개의 초밥을 먹음
while right < k:
    belt[sushi[right]] += 1
    right += 1

# 투 포인터 알고리즘을 활용하여 먹은 초밥의 갯수를 갱신
while left < n:
    belt[sushi[left]] -= 1
    # 0이 되는 것은 먹지 않은 초밥을 의미하므로, 가짓수를 셀 때 count되지 않도록 원소를 삭제
    if belt[sushi[left]] == 0:
        del belt[sushi[left]]
    
    belt[sushi[right]] += 1

    ans = max(ans, len(belt)) # len 함수로 key의 갯수를 count
    left += 1
    right += 1

print(ans)