[백준 2531] 회전 초밥

문제설명

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

2531번: 회전 초밥

알고리즘

이번 문제는 단순하게 반복문으로 결과를 구해낼 수 있다 

하지만 시간 제약이 있기 때문에 sliding window를 사용해야한다

k개를 확인해서 초밥의 갯수를 세기때문에 1칸씩 옮겨가며 연산한다

이때 모든 초밥을 다 다시세면 반드시 시간초과가 발생하기 때문에, 새로 추가되는 초밥만 세고 먹을 수 없는 초밥은 빼는 것이 문제의 해결 방식이다 

 

아래의 코드는 시간초과가 발생했던 방식이다

 

import sys 
 
def Input_Data(): 
    read = sys.stdin.readline 
    N, d, k, c = map(int,read().split()) 
    dish = [int(read()) for _ in range(N)] 
    return N, d, k, c, dish 
 
def Check():
    global visited
    cnt =0
    visited[c] += 1
    for i in range (1,d+1):
        if visited[i]>0:
            cnt +=1
    # print(visited)
    visited = [0 for i in range(d+1)]
    return cnt
 
def Solve():
    arr = []
    for i in range(0,N):
        for j in range(i,i+k):
            if j >= N: 
                j %= N 
            cur = dish[j]
            visited[cur] += 1
        # print(dish[i:i+k])
        arr.append(Check())
    return max(arr)
         
sol = 0 
# 입력
N, d, k, c, dish = Input_Data()  
visited = [0] * (d+1)
sol = Solve()
print(sol)

해당 방식으로 문제를 해결하니 시간초과가 발생했다

코드

import sys 
 
def Input_Data(): 
    read = sys.stdin.readline 
    N, d, k, c = map(int,read().split()) 
    dish = [int(read()) for _ in range(N)] 
    return N, d, k, c, dish 
 
def Check(cur_save): #sliding window를 한칸 옮겨 먹을 수 없는 초밥을 빼고 새로운 초밥 더하기
    sushi[cur_save]-=1
    cnt = len(sushi)
    if sushi[cur_save] == 0:
        del(sushi[cur_save])
    return cnt
 
def Solve():
    for i in range(k-1): #뒤로 이어질 초밥을 미리 저장 -> modulo로도 계산가능함 
        dish.append(dish[i])
    sushi[c] = 1 #쿠폰을 사용 초밥 미리 체크
    for i in range(0,k):
        cur = dish[i]
        if cur in sushi:
            sushi[cur] +=1
        else:#새로운 초밥인 경우
            sushi[cur] =1 
    res = Check(dish[0])#먹을 수 있는 초밥 수 반환
    if res == k+1:#최대 종류의 수를 먹을 수 있는 경우 연산 종료 
        return res
    
    for j in range(k, len(dish)):#초밥 종류 계산 -> sliding window를 한 칸 옮겨 연산 
        cur = dish[j]
        if cur in sushi:
            sushi[cur] +=1
        else:
            sushi[cur] =1     
        res = Check(dish[j-k+1])#초밥 가짓 수 확인
        arr.append(res)
    return max(arr)
         
sol = 0 
# 입력
N, d, k, c, dish = Input_Data() 
 
sushi = {}
# 함수실행
sol = Solve()
print(sol)

 

 

고찰

이번 문제는 sliding window의 필요성을 확실하게 느낄 수 있는 문제였다

반복되는 연산은 스킵하고 옮겨가면서 새로운 값만 조회하면 되서 시간초과를 피할 수 있었다

바꾼 코드도 줄일 수 있겠지만 시간이 모잘라 스킵했다