[백준] 2541번 : 회전초밥

문제

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

풀이

[백준] 2541 : 회전초밥 🥈(실버1)

• [알고리즘 : 브루트포스]

<✅ 풀이방법>

0. 회전은 마지막에서 k개 만큼만 접시 앞에꺼를 append시키자
1. slice를 해서 c(보너스 초밥) 값 없으면 slice한 것에 넣어주기

코드(code)

import sys

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


for n in range(N):
    plates.append(int(sys.stdin.readline()))
for i in range(k): # 회전을 해주기 위해서 더해줌
    plates.append(plates[i])

# 최대 초밥을 먹을 수 있는 가지수

answer = 0
for n in range(N):
    slice = []
    for i in range(n,n+k):
        slice.append(plates[i])
    if c not in slice:
        slice.append(c)
    answer= max(answer,len(set(slice)))

print(answer)

회고

• deque의 자료구조를 사용해서 문제를 풀었는데 시간초과 발생했다.
  deque의 자체는 좋은 자료구조이지만, slice해주는 과정 set함수 및 여러 자료구조 내에서 변환이 일어날때 시간복잡도가 원소의 개수만큼 필요하기 때문에 발생한 문제였다.

• [시간초과 발생 코드]

  https://github.com/joejames0830/ps_study/blob/main/Brute_Force/2531(%ED%9A%8C%EC%A0%84%EC%B4%88%EB%B0%A5).py