[백준] 15961 회전 초밥

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

초밥 벨트를 1차원 배열로 생성하고, K의 간격을 유지하며 연속해서 초밥들을 먹는 경우 탐색이 필요했습니다.

임시의 1차원 배열을 하나 생성하여 연속해서 먹는 초밥들을 기록하였습니다.

이후 집합을 이용하여 중복되는 초밥 종류를 하나로 인식하였고, 쿠폰의 초밥 종류도 집합에 추가하였습니다.

마지막으로 집합의 길이를 비교하며 최고 길이를 확인하였습니다.

 

그러나 배열을 이용하여 연속적으로 먹는 초밥의 종류를 기록하게 되면 배열을 계속해서 집합으로 변환하는 과정과 요소의 추가 제거, 집합의 길이를 카운트하는 과정이 필요하여 시간 초과 문제가 발생하였습니다.

 

이러한 문제를 해결하기 위해 초밥 종류의 개수만큼 크기의 1차원 배열을 생성하였고, 해당 초밥 종류를 선택하였는지 여부를 기록하였습니다.

이후 선택 여부에 따라 먹게 되는 초밥 종류의 개수를 숫자로 기록하였습니다.

처음 초밥 종류를 선택하면 1을 증가시키고, 해당 종류를 제거하여 먹지 않게 된다면 1을 감소시키는 방식을 이용하였습니다.

2) 알고리즘

• 두 포인터

3) 풀이 코드

사용 언어 - Python

import sys

N, D, K, C = map(int, sys.stdin.readline().split())     # 접시 수, 종류 수, 연속해서 먹는 수, 쿠폰 번호
sushi = []                  # 초밥들 목록
selected = [0] * (D+1)      # 초밥 종류별 선택 여부
selected[C] = 1             # 쿠폰 번호의 초밥 무조건 먹음
answer = 0                  

for _ in range(N):
    sushi.append(int(sys.stdin.readline()))             # 초밥 벨트의 정보

sushi.extend(sushi[:K-1])               # 초밥이 회전되므로 앞의 일부분을 뒤에 이어 붙임

ans = 1                                 # 쿠폰의 초밥은 항상 먹으므로 1로 시작
for i in range(N+K-1):
    s = sushi[i]                        # 현재 먹는 초밥 종류
    selected[s] += 1                    # 선택 +1
    if selected[s] == 1:                # 새로운 종류 먹는 경우
        ans += 1                        # 먹는 종류 개수 1 증가
    
    if i >= K-1:                        # 연속해서 먹기 시작하는 경우
                                        # (인덱스가 K-1일 때, 처음 연속해서 K개 먹게 됨)
        answer = max(answer, ans)       # 초밥 종류 많이 먹은 경우를 기록

        r = sushi[i-K+1]                # 다음 연속해서 K개 먹기 위해 앞에 제거될 초밥
        if r != C:                      # 쿠폰 초밥이 아닌 경우
            selected[r] -= 1            # 종류 선택 개수 -1
            if not selected[r]:         # 해당 종류 초밥을 안먹는 경우
                ans -= 1                # 먹는 종류 개수 -1

print(answer)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다