[백준/Python]2531: 회전 초밥

문제

https://www.acmicpc.net/problem/2531
백준 문제집 - 0x14강 - 투 포인터

 

알고리즘: 투 포인터, 브루트포스, 슬라이딩 윈도우

---

풀이

 

문제의 조건을 정리해보면 다음과 같다.

• 최대한 많은 종류의 초밥을 먹어야 함
• 먹을 수 있는 초밥의 갯수는 k개
• 쿠폰은 k개의 초밥과는 별개로 사용할 수 있음

마지막 조건 때문에 살짝 헷갈렸었다.
벨트 위의 연속된 k개의 초밥과 쿠폰초밥이 붙어있어야 하는 줄 알았는데 아니었다.

🟦쿠🟦🟦초1 초2 초3🟦🟦 ← 이런식으로 선택해도 상관없음

그냥 쿠폰초밥을 제외하고 선택한 접시가 k개이기만 하면 되는것이다.

 

또한 원형으로 돌아가는 벨트 위에 놓여있는 "회전" 초밥임을 유의해야한다.
따라서 주어진 초밥 대열을 리스트로 저장 후 [:k]만큼을 뒤에 추가해준 뒤 진행한다. (정확히 계산하면 [:k-1])

dish = [int(input()) for _ in range(N)]
dish.extend(dish[:k])  # 회전초밥이므로 원형탐색 고려

 

이제 투포인터로 탐색을 진행한다.
left는 0으로 설정, right을 0부터 N + k까지 늘려나가면서 조건을 체크한다.

때에 따라 각 포인터가 위치한 초밥의 종류, 그 초밥의 갯수를 확인해야 하므로 딕셔너리가 필요하다.
그리고 현재 선택한 초밥들의 종류 수는 변수cnt에 따로 저장한다.

1. 초밥을 하나씩 담고 딕셔너리에 해당 초밥의 갯수를 추가한다.
2. 먹어보지 않은 초밥이라면 cnt + 1
3. k그릇을 초과했을경우 => left 포인터 체크
   • 만약 left 초밥의 갯수가 1 이라면 cnt - 1
   • left 초밥의 갯수를 -1 해주고 left 포인터 한 칸 이동
4. 기존 최댓값과 현재 값을 비교
   • cnt + (쿠폰초밥이 k개에 포함되어있다면 0, 아니라면 1)

 

전체 코드

# 쿠폰초밥은 k개의 접시와는 별개로 사용할 수 있음.
# 메모리: 33432KB / 시간: 72ms
from sys import stdin


input = stdin.readline

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

dish = [int(input()) for _ in range(N)]
dish.extend(dish[:k])  # 회전초밥이므로 원형탐색 고려

sushi = {}

left = 0
ret = cnt = 0  # ret: 최댓값, cnt: 현재 먹은 초밥의 종류 갯수

for right in range(len(dish)):
    sushi[dish[right]] = sushi.get(dish[right], 0) + 1

    if sushi[dish[right]] == 1:  # 먹어보지 않은 종류라면 카운트
        cnt += 1

    # k그릇을 초과했을경우
    if (right-left+1) > k:
        if sushi[dish[left]] == 1:  # 만약 하나뿐인 스시였다면 카운트를 감해줌
            cnt -= 1
        sushi[dish[left]] -= 1
        left += 1

    # 먹은 초밥의 종류 + 쿠폰초밥이 포함되어있다면 0, 아니라면 1
    curr = cnt + (1 if sushi.get(c, 0) == 0 else 0)
    ret = max(ret, curr)

print(ret)

 

인생은 회전초밥.

 

그나저나 투포인터+딕셔너리 조합 문제가 꽤 많은것같다.

기본적인 투포인터 문제는 이분탐색에 많이 분포되어있으니 번갈아가며 풀면 좋을듯싶다~