[백준][파이썬] 2531번 회전초밥

 2531번 : 회전초밥

문제

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.

새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.

1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.

회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.

링크

2531번: 회전 초밥 (acmicpc.net)

2531번: 회전 초밥

 

 접근 방법

1. 문제에 정의된 n,d,k,c 값을 각각 입력 받고 회전 초밥(belt)도 list로 입력 받는다.
2. 초밥 가짓수의 최댓값(ans)을 0으로 초기화한다.
3. 가능한 초밥 종류의 가짓수를 모두 세기 위해(브루트 포스) for문을 이용한다.
   1. 먹을 수 있는 초밥 집합에는 처음과 끝이 있으므로 투 포인터 알고리즘을 사용한다. 
      • 집합의 크기는 k 이므로 처음 포인터와 끝 포인터의 차이를 k로 둔다.
      • 초밥이 회전식이므로 나머지를 이용하여 인덱스를 계산한다.
   2. 초밥의 가짓수를 세기 위해 집합의 중복 원소는 제거한다.
      • 이때 쿠폰으로 먹을 수 있는 초밥도 집합에 추가하여 집합의 중복 원소를 제거한다.
   3. 가짓수의 최댓값을 구하여야 하므로 max 함수로 최댓값을 가린다. 

1.  

+ 투포인터 참고 자료 : [알고리즘] 투 포인터(Two Pointers) — y-seo의 딩코 기록들 (tistory.com)

[알고리즘] 투 포인터(Two Pointers)

 

 풀이

 

1. set 함수

Python 자체 내장 함수로 unique한 집합이다. 즉 원소들이 중복되지 않는다.

set 함수에는 list를 넣어주어야 하며 set 함수를 거치면 자체 { } 형태가 되므로 list 함수를 사용해 다시 list 형으로 바꿔주어야 한다. 

s = list(set([1,2,2,3,4]))

s = [1,2,3,4]

 

2. 리스트 슬라이싱

리스트의 여러 개의 요소를 동시에 추출하고 싶을 때, 특히 연속적으로 접근하고 싶을 때 주로 사용한다.

시작 인덱스와 끝 인덱스를 콜론(:)을 사용하여 명시해주면 시작~끝 인덱스까지의 리스트 요소를 리스트로 반환한다.

이때 콜론 오른쪽에 들어갈 숫자는 ( 목표로 하는 끝 인덱스 + 1 ) 의 값이어야 한다.

day = ["mon", "tue", "wed", "thu", "fri", "sat", "sun"]
new = day[1:5]

new = ["tue", "wed", "thu", "fri"]

3. 나머지

회전식 즉 데큐와 유사한 앞 뒤가 연결된 리스트는 물론 데큐로도 풀 수 있지만.. 꼭 연결 링크가 필요한 것이 아니니 이번 문제처럼 나머지를 이용해 풀 수 있다.

i+k 값이 전체 리스트의 길이인 n 값을 넘어가게 된다면 (i+k)와 n을 나눈 나머지를 통해 인덱스를 알 수 있을 것이다.

    if ( i + k ) < n:
        temp = len(set(belt[i:i+k] + [c]))
    else:
        temp = len(set(belt[i:n] + belt[:(i+k)%n] + [c]))

 

 전체코드

import sys
input = sys.stdin.readline

n, d, k, c = map(int,input().split())
belt= [int(input()) for __ in range(n)]
ans = 0

for i in range(n):
    if ( i + k ) < n:
        temp = len(set(belt[i:i+k] + [c]))
    else:
        temp = len(set(belt[i:n] + belt[:(i+k)%n] + [c]))
    print(temp)
    ans = max(ans, temp)

print(ans)