15961. 회전 초밥 (Python)

15961번: 회전 초밥

 

풀이

 슬라이딩 윈도우를 사용하여 해결할 수 있는 문제이다. 연속으로 먹는 접시에 있는 초밥의 종류에 따른 개수를 카운트 할 수 있는 리스트를 하나 만들어 각 초밥의 개수를 카운트 해주었다. 문제를 해결하는 과정은 다음과 같다.

 

* kind : 현재 범위에서 초밥의 종류 개수, counts[n] : 현재 범위에서 n 종류 초밥의 개수, res : 초밥 종류의 최댓값

• 쿠폰 번호에 해당하는 초밥의 count를 하나 증가시키고 kind를 하나 증가시킨다.
• 처음 초밥부터 연속해서 먹는 접시의 수 만큼 범위를 탐색하여 count를 증가시킨다.
  • 이때 counts[n]이 0이었다면 kind를 하나 증가시킨다. 
• res를 kind로 초기화한다.
• 이제 접시를 한 칸씩 이동한다. 이 때, 처음에 있던 초밥의 종류의 counts를 감소시키고 마지막에 새로 추가되는 초밥의 종류의 counts를 증가시킨다. 
  • 문제의 예제에서 처음 초밥의 범위는 {7, 9, 7, 30}이다. 다음 초밥의 범위는 {9, 7, 30, 2}가 된다. 
  • 이 때 {9, 7, 30}은 중복되는 초밥이기 때문에 따로 처리해 줄 필요가 없다. 제외되는 7에 대해서 counts[7]을 하나 감소시키고 추가되는 2에 대해서 counts[2]를 하나 증가시키면 된다.
• counts[n]을 감소시킬 때, counts[n]이 0이 된다면 kind를 하나 감소시킨다.
• counts[m]을 증가시킬 때, counts[m]이 1이 된다면 이는 새로운 초밥 종류가 생긴 것이기 때문에 kind를 하나 증가시킨다.
• 마지막에 res와 kind중 큰 값으로 res를 변경한다.
• 위와 같은 과정을 마지막 초밥까지 반복해주면 된다.

 

코드

if __name__ == '__main__':
    # N : 회전 초밥 벨트에 놓인 접시의 수
    # d : 초밥의 가짓수
    # k : 연속해서 먹는 접시의 수
    # c : 쿠폰 번호 
    N, d, k, c = map(int, input().split()) 
    dishes = []
    counts = [0] * (d+1) # counts[n] : 현재 범위에서 n번 종류의 초밥의 개수

    for i in range(N):
        dishes.append(int(input()))

    counts[c] += 1 # 쿠폰 번호에 해당하는 초밥 종류 개수를 하나 증가시킨다.
    kind = 1 # 현재 범위의 초밥 종류는 쿠폰 번호에 해당하는 초밥 하나가 있다.

    for i in range(k): # 처음 0번부터 k-1번까지 초밥 범위를 잡는다.
        if counts[dishes[i]] == 0: # 현재 초밥 종류가 0이었다면 새롭게 되는 초밥 종류이므로 kind를 1 증가시킨다.
            kind += 1
        counts[dishes[i]] += 1
    res = kind # 처음 초밥 가짓수의 최댓값은 kind로 초기화해준다.

    endPoint = k-1 # 현재 범위의 마지막 초밥 인덱스 번호
    for i in range(1, N): # 이제 1번째부터 N-1번째까지 범위를 옮겨가며 탐색한다.
        endPoint = (endPoint + 1) % N # 처음과 끝이 이어져 있으므로 나머지 연산을 사용하여 endPoint를 갱신한다.

        start = dishes[i-1] # 범위에서 제거될 초밥의 종류
        end = dishes[endPoint] # 범위에 새롭게 추가될 초밥의 종류

        counts[start] -= 1 # start에 해당하는 초밥 종류의 개수를 감소시킨다.
        if counts[start] == 0: # 만약 0이 되었다면 초밥의 종류가 줄어들었으므로 kind를 1 감소시킨다.
            kind -= 1

        counts[end] += 1 # end에 해당하는 초밥 종류의 개수를 증가시킨다.
        if counts[end] == 1: # 만약 1이 되었다면 새로운 종류가 생긴것이므로 kind를 1 증가시킨다.
            kind += 1

        res = max(res, kind) # 현재 범위에 있는 초밥의 종류와 res중 큰 값으로 res를 갱신한다.

    print(res)