새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

[백준] 15961 회전 초밥

by 언호 2022. 7. 16.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 1719 택배  (0) 2022.07.18
[백준] 6087 레이저 통신  (0) 2022.07.17
[백준] 10217 KCM Travel  (0) 2022.07.15
[백준] 6549 히스토그램에서 가장 큰 직사각형  (0) 2022.07.14
[백준] 14226 이모티콘  (0) 2022.07.13

댓글