문제 링크

문제 소개

해당 문제는 양 끝이 연결된 컨베이어 벨트에 연속된 스시 접시 k개를 잡을 때 종류가 최대인 값을 구하는 문제이다.

문제 분석

문제를 처음 봤을 때 sliding window 알고리즘을 통해 풀수있음을 알 수 있었다.

# fail 1
import sys


def getSushiCnt(arr):
    return len(list(set(arr)))


def sushi(d, k, c, belt):
    maxValue = -1
    for i in range(0, N):
        part = belt[i:i + k] if i < N - k else belt[i:] + belt[:i + k - N]
        maxValue = max(maxValue, getSushiCnt(part) + 1 if c not in part else getSushiCnt(part))
    print(maxValue)


def solution():
    global N
    N, d, k, c, = map(int, input().split())
    belt = []
    for _ in range(N):
        belt.append(int(input().rstrip('\n')))

    sushi(d, k, c, belt)

이러한 방식으로 리스트 슬라이싱을 통해 sliding window를 구현하여 set을 통해 종류를 알아내서 답을 출력했다.

하지만 이러한 방식은 시간초과가 발생하였다.

이유는 아래와 같다.

1. 2 ≤ N ≤ 30,000인데 이러한 방식으로 슬라이싱을 진행
2. 종류를 알아내기 위해 중복제거시 자주 사용하는 set 사용

우선 1번 문제부터 처리하기 위해 아래와 같이 코드를 작성하였다.

# fail 2
import sys
from collections import deque


def getSushiCnt(arr):
    return len(list(set(arr)))


def sushi(d, k, c, belt):
    maxValue = -1
    part = deque(belt[:k])
    for i in range(N - 1):
        maxValue = max(maxValue, getSushiCnt(part) + 1 if c not in part else getSushiCnt(part))
        part.popleft()
        part.append(belt[(i + k) % N])
    print(maxValue)


def solution():
    global N
    N, d, k, c, = map(int, input().split())
    belt = []
    for _ in range(N):
        belt.append(int(input().rstrip('\n')))
    sushi(d, k, c, belt)


solution()

이러한 방식은 기존의 방식에서 슬라이싱 방식을 사용하지않고 deque를 사용해서 왼쪽 값을 지우고 오른쪽 값을 추가하여 진행하였다. 하지만 이러한 방식도 시간 초과가 발생하였다.

2번 문제를 해결하기 위해서 종류를 set을 사용하지않고 다른 방식을 사용해야한다. sliding window를 구현하기 위해 해당 접시의 종류에 자주 접근하기 위해 dict로 바꿔 진행해보았다.

deque에서 dict로 바꾸는 과정에서 popleft, append함수를 통해 sliding window를 구현하는 것에 제약이 걸렸다(dict에는 순서가 없기 때문).

그럼으로 두 포인터를 sliding window 알고리즘을 구현하였다.

해결책 1 (pointer, dict, sliding window)

import sys
from collections import Counter


def sushi(d, k, c, belt):
    left, right = 0, k - 1
    part = Counter(belt[:right + 1])
    if part.get(c):
        part[c] += 1
    else:
        part[c] = 1
    ans = -1
    while left < N:
        ans = max(ans, len(part))
        part[belt[left]] -= 1
        if part[belt[left]] == 0:
            del part[belt[left]]
        right = (right + 1) % N
        part[belt[right]] += 1
        left = left + 1
    print(ans)


def solution():
    global N
    input = sys.stdin.readline
    N, d, k, c, = map(int, input().split())
    belt = []
    for _ in range(N):
        belt.append(int(input().rstrip('\n')))
    sushi(d, k, c, belt)


solution()

해결책 2 (pointer, list, slding window)

이 코드는 리스트를 기반으로 pointer돌렸다. 문제에서 접시의 종류는 정해져있음으로 아래의 코드와 같이 초기값을 갖을 수 있다.

	checkList = [0 for _ in range(D + 1)]
    cnt, ans = 0, 0

여기서 우선 checkList의 역할은 접시의 개수를 인덱스로 저장해둔 것이다(만약 여기서 1번 접시가 들어올 경우 checkList[1] += 1를 해주는 느낌).

이러한 방식으로 먼저 0번째부터 k번째까지 연속된 접시들을 우선 집어넣는다. 집어넣을 때, 1이 될 경우(접시가 없었는데 넣어서 생기는 경우) 현재 접시의 종류(cnt)를 +1해준다.

이러한 방식으로 앞서 counter함수를 사용한 것처럼 리스트에 각 인덱스별 접시 개수를 넣을 수 있다.

    for k in range(K):
        checkList[belt[k]] += 1
        if checkList[belt[k]] == 1:
            cnt += 1

해결책 1과 마찬가지로 두 포인터를 둘 건데, 왼쪽 포인터(front)는 0부터 N-1까지 end 는 front부터 front + K까지 포인터로 둔다.

여기서 리스트의 양쪽이 연결되어있기 떄문에, front포인터가 N-K보다 클 때 리스트의 끝을 넘어가게 되기 때문에 이를 처리해주기 위해 아래와 같이 back포인터를 지정해두었다.

    for front in range(N):
        back = front + K if front < N - K else (front + K) - N

이렇게 지정한 두 포인터(front,back)를 기준으로 front에서는 뺴고 back에서는 접시를 추가하는 식으로 진행한다.

이러한 방식으로 진행될 때, 앞에서 리스트의 값(접시의 수)가 1이 될 경우(접시가 없었는데 생기는 경우)에는 접시 종류(cnt)를 +1 해준다.

반대로, 접시를 뺴는 경우에 만약 리스트의 값(접시의 수)가 0이 될경우(접시가 있었는데 없어지는 경우)에는 접시 종류(cnt)를 -1 해준다.

이러한 알고리즘을 아래와 같이 구현하였다.

        checkList[belt[front]] -= 1
        if checkList[belt[front]] == 0:
            cnt -= 1

        checkList[belt[back]] += 1
        if checkList[belt[back]] == 1:
            cnt += 1

이렇게 진행하고 나서, 마지막으로 쿠폰 처리를 해야하는데 리스트값이 있을 경우(이미 해당 스시가 있는 경우) cnt를 비교하고 리스트값이 없는 경우(해당 쿠폰 스시가 없는 경우)에는 cnt + 1를 해준다.

        ans = max(ans, cnt + 1) if checkList[C] == 0 else max(ans, cnt)

이러한 방식으로 해결책 1보다 2배 빠르게 문제가 해결된다.

아래는 해당 전체 코드이다.

import sys


def sushi(belt):
    checkList = [0 for _ in range(D + 1)]
    cnt, ans = 0, 0
    for k in range(K):
        checkList[belt[k]] += 1
        if checkList[belt[k]] == 1:
            cnt += 1
    for front in range(N):
        back = front + K if front < N - K else (front + K) - N
        checkList[belt[front]] -= 1
        if checkList[belt[front]] == 0:
            cnt -= 1

        checkList[belt[back]] += 1
        if checkList[belt[back]] == 1:
            cnt += 1
        ans = max(ans, cnt + 1) if checkList[C] == 0 else max(ans, cnt)
    print(ans)


def solution():
    global N, D, K, C
    input = sys.stdin.readline
    N, D, K, C = map(int, input().split())
    belt = [int(input().rstrip('\n')) for _ in range(N)]
    sushi(belt)


solution()