[BOJ_2531] 회전 초밥

 

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

2531번: 회전 초밥

 

✅ 내 풀이(Success) :

 

🚩 Idea:

 1. 일단 문제에서 N의 수가 최대 30,000으로 꽤 크다. 이때는 입력을 받는 시간을 최대한 줄이기 위해 빠른 입출력을 사용하자. 

 2. 회전하는 벨트를 보고 데큐의 rotate() 함수를 떠올랐다.

 3. 문제에서 구하고자 하는 값은 '최대한 많은 종류의 초밥을 먹고, 그 수를 반환하는 것'이다. 그럼 어떤 경우에 이 값이 최대가 될까? 연속된 k개의 초밥이 모두 다른 종류이고, 그 안에 쿠폰으로 먹을 수 있는 초밥이 들어있지 않는 경우이다. 따라서 나올 수 있는 정답의 최대 값은 k+1이다.

 4. 데큐를 이용해 N의 값만큼 회전시키면서 0번째 인덱스에서 k개의 초밥을 확인한다. 같은 종류의 초밥을 제거하기 위해 집합을 사용한다.

  중요한 포인트는 데큐에서는 list에서 처럼 직접적으로 슬라이싱을 할 수 없다. 따라서 collections 모듈의 islice 함수를 이용하여 데큐에서 일부분을 추출한다.

5. 나머지 과정은 데큐를 회전시키면서 모든 경우를 4번의 과정을 통해 확인하면 된다.