백준 2531. 회전초밥

💡문제 분석 요약

• 회전 초밥 벨트에는 같은 종류의 초밥이 2개 이상 있을 수 있다.
• 벨트 위에 임의의 한 위치부터 k개 접시를 연속해서 먹을 경우 → 할인된 정액 가격으로 제공한다.
• 초밥 종류 중 1개가 적힌 쿠폰이 발행되고, k개 연속으로 먹는 행사 참여하면, 쿠폰에 적힌 초밥 1개가 무료로 제공된다.
  • 만약 그 쿠폰 초밥이 벨트에 없으면 따로 만들어서 주게 된다.
• 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구해라.

<아이디어>

회전하는 벨트에 있는 초밥이니까 일단 리스트에 넣어 (인덱스 : 0~n-1)

연속된 k개 초밥 선택하기

• 연속해서 k개를 선택할거야.
• 임의의 한 지점에서 말이야??
• 그러면 나는 총 n개의 시작 지점을 선택할 수 있지.
• i부터 i+k-1번째 까지 포함되겠지?
• 근데 회전 초밥이야.
  • 0,1,2,3,4,5 이렇게 있을 때, k=3
  • 0,1,2 / 1,2,3 / .. / 4,5,0 / 5,0,1 /
  • 시작 인덱스가 m일 때, 끝 인덱스는 (m+k-1)%n
  • 근데 나는 회전 초밥 길이를 그대로 유지하면서 한 바퀴만 돌면서 k개가 있는 연속된 순열을 만들면 되니까 arr 끝에다가 arr 앞에서부터 k-1개를 붙이면 그냥 선형 순회할 수 있네

⇒ left, right 사용해서 O(N)만에 탐색하기

선택한 연속된 k개 초밥이 max 가짓수인지 보기

⇒ 각 O(N)에 내부 로직으로 존재한다.

• 중복된 숫자들이 있는 경우를 확인해서 선택한 k개의 초밥 가짓수 계산하기
  • set해서 크기 만들기
• 쿠폰에 있는 초밥이 가짓수+1 하게 만드는지 확인하기
• 최종 가짓수를 hq에 넣기

최종 가짓수 출력

2 ≤ 벨트 위 회전 초밥 접시 수 N ≤ 3*10^4

2 ≤ 초밥 가지 수 d ≤ 3*10^3

2 ≤ 연속해서 먹는 접시 수 k ≤ 3*10^3 (k≤N)

1 ≤ 쿠폰 번호 c ≤ d

1 ≤ 초밥 종류 나타내는 정수 ≤ d

시간 제한 : 1초

입출력

• 입력

8 30 4 30 # N, d, k, c
7 # 한 위치에서 회전 방향 따라갈 때 놓여진 초밥 번호
9
7
30
2
7
9
25

 

• 출력

  5

💡알고리즘 설계 (수도 코드)

1. 회전하는 벨트에 있는 초밥이니까 일단 리스트에 넣어 (인덱스 : 0~n-1)
2. 원형 리스트로 사용하는 것 처럼 선형 리스트로 만들기
3. 연속된 k개 초밥 선택하기
   • left는 0부터 n까지 돈다.
     • right = left+k
     • k_arr = set(dishes[left:right])
       : 중복된 숫자들 제거
     • k_arr.add(c) 쿠폰에 있는 초밥이 가짓수+1 하게 만드는지 확인하기
   • 최종 가짓수 len(k_arr)를 hq에 넣기
4. ⇒ left, right 사용해서 O(N)만에 탐색하기
5. 최종 가짓수 출력

💡코드

35772 KB	2820 ms

import sys
import heapq

n,d,k,c = map(int, sys.stdin.readline().strip().split())
dishes = []
for _ in range(n): #O(N)
    dishes.append(int(sys.stdin.readline().strip()))
dishes += dishes[:k-1]

res = []
for left in range(n): #O(N)
    right = left+k
    k_arr = set(dishes[left:right]) #O(k)
    k_arr.add(c)
    heapq.heappush(res, -len(k_arr)) #O(logk)

print(-res[0])

💡시간 복잡도

O(Nk) = O(910^8)

⇒ 엥 근데 .. 왜 시간 초과가 안 나지?

💡 다른 풀이

틀리진 않았지만 시간 복잡도 계산 상 시초가 날 확률이 높기 때문에 새로우 풀이를 생각해보자.

import sys

n, d, k, c = map(int, sys.stdin.readline().strip().split())
dishes = [int(sys.stdin.readline().strip()) for _ in range(n)]
dishes += dishes[:k-1]  # 원형을 선형으로 처리하기 위해

sushi_count = {c: 1}  # 쿠폰 초밥은 항상 포함
max_types = 1

# 초기 윈도우 설정
for i in range(k):
    sushi_count[dishes[i]] = sushi_count.get(dishes[i], 0) + 1
max_types = len(sushi_count)

# 슬라이딩 윈도우 이동
for i in range(1, n):
    left = i - 1
    right = i + k - 1

    # 왼쪽 끝 초밥 제거
    sushi_count[dishes[left]] -= 1
    if sushi_count[dishes[left]] == 0:
        del sushi_count[dishes[left]]

    # 오른쪽 끝 초밥 추가
    sushi_count[dishes[right]] = sushi_count.get(dishes[right], 0) + 1

    # 최대 종류 개수 갱신
    max_types = max(max_types, len(sushi_count))

print(max_types)

💡 느낀점 or 기억할 정보

• 원형 리스트를 k씩 묶어서 1번만 순회할 때 선형 리스트로 바꾸는 방법
  • dishes += dishes[:k-1]
• 슬라이딩 윈도우 알고리즘과 투포인터 알고리즘의 차이
  • 슬라이딩 윈도우
    • 개념
      • 리스트의 항목을 순차적으로 탐색할 때, 고정된 크기의 윈도우를 이동시키면서 주어진 조건을 만족하는 부분을 찾는 방법입니다.
      • 윈도우의 크기는 고정되어 있거나 가변적일 수 있습니다.
      • 이 알고리즘은 주로 연속된 데이터의 최대합, 최소값, 중간값 등을 효율적으로 계산할 때 사용됩니다.
    • 예시
      : 구간을 사용할 때
      • 최대 합 구하기: 고정된 크기의 윈도우를 이용해 배열 내 연속된 항목들의 최대 합을 구할 수 있습니다.

      • # 예시: 주어진 배열에서 크기가 k인 모든 연속 부분 배열의 최대 합을 찾는 문제
        def maxSum(arr, k):
            n = len(arr)
            if n < k:
                print("Invalid")
                return -1
        
            # 윈도우의 첫 부분을 계산
            window_sum = sum(arr[:k])
            max_sum = window_sum
        
            # 슬라이딩 윈도우를 이동
            for i in range(n - k):
                # 현재 윈도우에서 첫 번째 요소를 제거하고 다음 요소를 추가
                window_sum = window_sum - arr[i] + arr[i + k]
                # 최대 합 갱신
                max_sum = max(max_sum, window_sum)
        
            return max_sum
        
        # 슬라이딩 윈도우: 고정된 크기의 윈도우를 이동시키며 문제를 해결

      • 중복 문자 없는 가장 긴 부분 문자열 찾기: 가변적인 크기의 윈도우를 이용해 조건을 만족하는 최대 길이를 찾습니다.
  • 투 포인터
    •  개념
      • 이 두 포인터는 보통 배열의 시작과 끝에서 시작하거나 같은 위치에서 시작하여 서로를 향해 이동하거나 멀어지면서 주어진 조건을 만족하는 요소를 찾습니다.
      • 주로 정렬된 배열에서 두 수의 합, 차이, 비율 등을 만족하는 요소를 찾을 때 사용됩니다.
    • 예시
      : 두 수를 사용할 때
      • 합이 특정 값에 해당하는 두 요소 찾기: 정렬된 배열에서 두 포인터를 이용해 합이 특정 값에 해당하는 요소를 효율적으로 찾을 수 있습니다.

      • # 예시: 정렬된 배열에서 두 수의 합이 특정 값에 도달하는 쌍을 찾는 문제
        def twoSum(numbers, target):
            left, right = 0, len(numbers) - 1  # 배열의 양 끝에서 시작하는 두 포인터
        
            while left < right:
                current_sum = numbers[left] + numbers[right]  # 현재 두 포인터가 가리키는 요소의 합
        
                if current_sum == target:  # 목표값에 도달한 경우
                    return [left + 1, right + 1]
                elif current_sum < target:  # 합이 목표값보다 작은 경우, 왼쪽 포인터 이동
                    left += 1
                else:  # 합이 목표값보다 큰 경우, 오른쪽 포인터 이동
                    right -= 1
        
            return []
        
        # 투 포인터: 조건에 따라 포인터를 이동시키며 문제를 해결, 포인터가 가리키는 범위의 크기는 변할 수 있음

      • 배열에서의 최소 차이 찾기: 두 포인터를 이용해 배열 내 두 요소 간의 최소 차이를 찾을 수 있습니다.
  • 요약
    • 슬라이딩 윈도우는 연속된 데이터의 특정 조건을 만족하는 부분을 찾을 때 사용되며, 윈도우의 크기가 중요한 역할을 합니다.
      투 포인터는 주로 정렬된 배열에서 두 요소의 관계(합, 차이 등)를 만족하는 요소를 찾을 때 사용됩니다.
      즉, 윈도우와 포인터의 차이 !