[백준] 2531 - 회전 초밥

1. 문제

2531번: 회전 초밥

2. 개요

회전초밥 가게에서 두가지 이벤트를 동시에 진행한다.

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

회전벨트의 상태, 초밥의 가짓수, 연속으로 먹을 접시의 개수, 쿠폰으로 받은 초밥의 종류가 각각 주어졌을 때, 손님이 먹을 수 있는 초밥의 최대 종류를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

회전초밥 벨트는 처음과 끝이 없이 이어져있는 상태이므로 입력받은 리스트도 그에 맞추도록 한다.

마지막 값부터 최대로 연속으로 집었을 경우 k-1번째까지 선택이 가능하도록 처음부터 k-1번째까지를 맨 뒤에 추가한다.

리스트의 첫 값부터 k까지의 값을 집합에 넣고, 이 집합의 크기를 현재까지의 최댓값과 비교한다.

집합의 크기가 최댓값과 같거나 더 크다면, 쿠폰 초밥의 여부를 확인한다.

쿠폰 초밥이 포함되어있다면 종류가 더 늘어날 수 없으므로 집합의 크기를 답으로 갱신하고, 포함되어있지 않다면 1종류를 더 먹을 수 있게 되므로 집합의 크기 + 1을 답으로 갱신한다.

3-2. Python

import sys

N, d, k, c = map(int, sys.stdin.readline().split())

sushis = []

for i in range(N):
    sushis.append(int(sys.stdin.readline()))

sushis = sushis + sushis[:k]

l = 0
r = l + k
sset = set()
answer = 0

while l <= N:
    sset = set(sushis[l:r])

    if len(sset) >= answer:
        if c in sset:
            answer = len(sset)
        
        else:
            answer = len(sset) + 1

    l += 1
    r += 1

print(answer)

3-3. C#

namespace boj_2531
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            int N = int.Parse(input[0]), d = int.Parse(input[1]), k = int.Parse(input[2]), c = int.Parse(input[3]);

            List<int> sushis = new();
            List<int> tmp = new();

            for (int i = 0; i < N; i++)
                sushis.Add(int.Parse(sr.ReadLine()));

            sushis = sushis.Concat(sushis.GetRange(0, k - 1)).ToList();

            int l = 0;
            int r = l + k;
            HashSet<int> sset = new();

            int answer = 0;

            while (l < N)
            {
                sset = sushis.GetRange(l, k).ToHashSet();

                if (sset.Count() >= answer)
                {
                    if (sset.Contains(c))
                        answer = sset.Count();

                    else
                        answer = sset.Count() + 1;
                }

                l++;
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}