김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 3689 셔플 파이썬(Python)

문제 링크

슬라이딩 윈도우(Sliding Window)를 활용하는 문제.
처음에 국문으로 몇번을 읽어도 문제가 이해가 안 돼서 원문을 찾아서 읽었다.
국문으로는 “다음 셔플이 어떻게 되는지”라고 나와 있는데, 정확히는 다음 셔플이 가능한 위치(Future Position)가 몇 군데인지 찾는 문제이다.
이를테면 예제의 첫번째 케이스는 3 4 / 4 1 3 2 / 1 2 3 4로 끝나므로 바로 다음 곡부터 셔플이 이루어져야 하므로 답은 1이고, 두번째 케이스는 6 / 5 4 3 2 1(다다음 곡부터 셔플)부터 6 5 4 3 2 1 /(다음 곡부터 셔플)까지 6가지 경우가 있으므로 답은 6이다.
따라서 다음 셔플의 위치를 찾는 문제는 사실상 현재 리스트에서 처음과 마지막 플레이리스트가 몇 곡을 포함하고 있는지(또는 현재 리스트에서 플레이리스트를 어떻게 나눌 수 있는지) 확인하는 것과 동일하다.
기본적인 아이디어는 일단 가능한 모든 플레이리스트에서 겹치는(중복되는) 음악이 있는지를 조사하는 것이다.
처음과 마지막의 플레이리스트는 굳이 s곡이 아니라 1곡부터 가능하므로 나올 수 있는 플레이리스트는 \(n + s - 1\)개이므로 충분히 주어진 시간 안에 할 수 있다.
처음과 마지막을 제외한 플레이리스트는 길이가 고정적이므로 슬라이딩 윈도우를 사용하고, 처음과 마지막의 경우를 해결하기 위해(정확히는 \(n<s\)인 경우 중에만) 주어진 리스트에 0으로 패딩을 하고 예외처리를 해 주었다.
예를 들어 3 5\n1 2 3 1 3라는 예제가 있다고 하면, 1, 1 2, 1 2 3, 2 3 1, 3 1 3, 1 3, 3가 가능한 플레이리스트일 것이다.
이중 3 1 3은 겹치는 음악이 있으므로 이 경우는 일어날 수 없다.
이제 이 플레이리스트들을 s개(이 경우는 3개) 간격으로 모은다.
그러면 1 / 2 3 1 / 3(다다다음 곡부터 셔플), 1 2 / 3 1 3(불가능), 1 2 3 / 1 3(다다음 곡부터 셔플)의 3가지 경우가 나온다.
이 중 3 1 3을 포함하는 두 번째 경우는 불가능하므로 최종적으로 가능한 경우는 2가지가 된다.

#!python

from sys import stdin
input = stdin.readline

t = int(input())
for _ in range(t):
    s, n = map(int, input().split())
    # 이전까지의 기록, 뒤에 0으로 패딩을 해서 아래 for문에서의 인덱스에러를 방지했다
    history = list(map(int, input().split())) + ([0] * (2 * (s - n)))
    # valid[i]는 i번째 아이템에서 시작한 길이 s의 수열이 규칙에 맞는지를 의미
    # i의 범위는 -s+1 < i < n-1
    valid = [True for _ in range(n + s)]
    # 해당 곡이 이전 s곡 내에 몇 번 실행되었는지를 나타냄
    played = [0 for _ in range(s + 1)]
    # 이전 s곡 내에 같은 곡이 중복 등장한 횟수
    duplicated = 0

    # s보다 작을 수 있는 처음 구간
    for i in range(-s + 1, 1):
        # 이전에 False가 한 번이라도 나오면 이후로는 쭉 False다
        valid[i] = valid[i-1]
        # 새로 등장한 노래가 중복된 노래라면 중복 횟수를 증가시키고 valid는 False
        if played[history[i+s-1]]:
            valid[i] = False
            duplicated += 1
        # 만약 0으로 패딩된 부분이 아니라면 재생횟수를 증가시킴
        if history[i+s-1]:
            played[history[i+s-1]] += 1

    # 길이가 무조건 s인 구간
    for i in range(1, n - s + 1):
        # 윈도우 뒷부분 : 0으로 패딩된 부분이 아니라면 재생횟수를 감소시킴
        if history[i-1]:
            played[history[i-1]] -= 1
        # 재생횟수가 감소한 뒤에도 남아있다면 중복된 노래였다는 것이므로 중복 횟수 감소
        if played[history[i-1]]:
            duplicated -= 1
        # 윈도우 앞부분 : 중복된 노래인지 확인하고 중복 횟수 증가
        if played[history[i+s-1]]:
            duplicated += 1
        # 0으로 패딩된 부분이 아니라면 재생횟수를 증가시킴
        if history[i+s-1]:
            played[history[i+s-1]] += 1
        # 만약 중복된 노래가 한 곡이라도 있다면 valid를 False로
        if duplicated:
            valid[i] = False

    # 길이가 s보다 작아지는 마지막 구간
    for i in range(n - s + 1, n):
        # 0으로 패딩된 부분이 아니라면 재생횟수를 감소시킴
        if history[i-1]:
            played[history[i-1]] -= 1
        # 중복된 노래였다면 중복 횟수 감소
        if played[history[i-1]]:
            duplicated -= 1
        # 만약 중복된 노래가 한 곡이라도 있다면 valid를 False로
        if duplicated:
            valid[i] = False
    
    # 가능한 경우는 최대 s개
    ans = s
    # 모든 경우 중 중복되는 노래가 한번이라도 나온 경우가 있으면 답을 1씩 뺌
    for i in range(-s + 1, 1):
        for j in range(i, n, s):
            if not valid[j]:
                ans -= 1
                break
    
    print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑