백준 15961 회전 초밥

회전 초밥

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• 더블포인터 문제

1. 연속된 노드를 탐색할 때, 범위 내 양끝 노드만 추가,삭제하여 중복된 노드의 탐색비용을 줄인다.
2. 나온 노드들의 수를 딕셔너리를 이용하여 카운트한다.
3. 쿠폰 노드는 미리 딕셔너리에 반영한다.

✔ 코드

import sys, copy
from collections import deque

def solution(d,k,c,nodes):
    answer = 1
    lp, rp = 0, 0
    window = deque()
    dic_window = {(node+1):0 for node in range(d)}
    dic_window[c] += 1   # 쿠폰은 미리 추가
    max_answer = 1
    
    # 초기 k개의 노드
    for i in range(k):
        rp += 1
        window.append(nodes[i])
        dic_window[nodes[i]] += 1
        
        if dic_window[nodes[i]] == 1:
            answer += 1

    # 왼쪽 포인터가 마지막까지 도달하면 종료
    while( lp != len(nodes)-1 ):

        # 왼쪽 포인터 이동
        elem = window.popleft()
        dic_window[elem] -= 1
        lp += 1
        if dic_window[elem] == 0:
            answer -= 1

        # 오른쪽 포인터 이동
        window.append(nodes[rp])
        dic_window[nodes[rp]] += 1
        if dic_window[nodes[rp]] == 1:
            answer += 1

        rp += 1
        # 오른쪽 노드는 넘어가면 왼쪽끝으로 이동
        if rp == len(nodes) :
             rp = 0

        if answer > max_answer:
            max_answer = answer


    # print(window)
    print(max_answer)

    return


if __name__ == "__main__":
    N, d, k, c = map(int, input().split())
    nodes = []
    for _ in range(N):
        nodes.append(int(sys.stdin.readline().rstrip()))
    solution(d, k, c, nodes)

☝ 팁

• 셋을 이용해서 중복체크를 할수도 있지만, 두개의 원소가 있을때 처리하기가 복잡해진다.
  때문에, 딕셔너리를 사용하면 좋다.
• 쿠폰은 늘 반영하기 때문에 미리 추가해놓으면 된다.