[백준] 2531 - 회전 초밥

백준 2531번 회전 초밥

 

✅문제 링크 : https://www.acmicpc.net/problem/2531

 

이 문제는 순서대로 k 개의 초밥을 먹을 때, 먹을 수 있는 가장 다양한 초밥의 가짓수를 구하는 문제이다. 다른 복잡한 알고리즘이 쓰이지 않고 순서대로 확인해서 최적의 답을 찾아야 한다. 

처음에는 아주 단순하게 d+1을 길이로 하는 visited 배열에 현재의 i부터 i+k 까지의 값에 대해 True를 작성하고 count 함수를 이용해서 True의 개수를 파악했지만, count 함수가 n(d) 의 시간복잡도를 가지기 때문에 반복문에서 거의 n*n 보다 큰 시간 복잡도를 가지게 되었고, '시간 초과'로 실패했다. 

 

따라서 최대한 중복되는 계산을 줄이고자, 슬라이딩을 이용했다. 

 

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 연속된 데이터에서 일정 크기의 윈도우가 있을 때 이 윈도우를 하나씩 이동시키면서 데이터를 처리하는 기법이다. 순차 자료구조에서 연속적인 구간을 처리해야 하는 일이 반복될 때, n*n 의 시간 복잡도를 n 으로 줄일 수 있는 방법이다. 윈도우를 옮길 때마다 이전과 겹치는 부분은 재사용하고, 새로 추가되는 원소를 더하고 제거되는 원소를 빼는 단순 계산 방식으로 시간 복잡도를 줄일 수 있다. 

이미지 출처 : https://velog.io/@wlwl99/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%ED%85%8C%ED%81%AC%EB%8B%89

 

➡️참고한 블로그 링크 : https://velog.io/@wlwl99/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%ED%85%8C%ED%81%AC%EB%8B%89

슬라이딩 윈도우 테크닉

 

 

 

그럼에도 불구하고 사실 깨나 복잡하게 구현했는데, visited 배열을 boolean 값이 아닌 수로 넣어서, 이전 요소를 뺄 때 visited이 0이 되면 현재 슬라이드 안에 해당 요소가 없다는 뜻이므로 cand(현재 슬라이드의 초밥 종류 수)에서 1을 빼고, 새로운 요소를 추가할 때도 visited가 정확히 1이라면 새로 추가된 초밥 종류이므로 cand에 1을 더해서 최대 종류 수 val 과 max 값을 비교한다. 

 

이 방법 말고, set을 사용하면 요소를 넣고, 빼거나 len으로 요소의 수를 세는 데 훨씬 빠르고 편리하다. list가 아닌 set을 사용하는 이유는, set은 해시 테이블로 구현되어 있기 때문에 모든 인덱스를 순회하는 게 아니라 값을 해시함수로 변환해서 인덱스를 찾으므로 단순 계산이라 O(1) 의 시간 복잡도를 가진다. 이 원리는 파이썬의 딕셔너리에도 똑같이 적용되므로, 만약 값을 저장해야 하는데 주어진 시간이 적을 때 set이나 dic을 사용하는 걸 알아두는 것도 좋을 것 같다.

 

➡️풀이 참고한 블로그 : https://velog.io/@junseyeon/%EB%B0%B1%EC%A4%80-2531%EB%B2%88-%ED%9A%8C%EC%A0%84%EC%B4%88%EB%B0%A5-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

n,d,k,c=map(int,input().split(' '))

lst=[int(input()) for _ in range(n)]

val=1
visited=[0]*(d+1)
visited[c]=1

for j in range(k):
    visited[lst[j%n]]+=1
    if visited[lst[j%n]]==1:
        val+=1

cand=val

for i in range(1,n):
    visited[lst[i-1]]-=1
    if visited[lst[i-1]]==0:
        cand-=1

    visited[lst[(i+k-1)%n]]+=1
    if visited[lst[(i+k-1)%n]]==1:
        cand+=1
    
    val=max(val, cand)
    

print(val)