김낭만

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

백준(BOJ) 2433 The Sound of Silence 파이썬(Python)

문제 링크

이상한 방법으로 푼 문제.
구간의 최대, 최소를 계속해서 구해야 하는 문제.
정석은 세그먼트 트리(Segment Tree)나 데크(Deque)를 이용하는 것이다.
그런데 어쩌다 보니 우선순위 큐를 사용하는 애드 혹스러운 방법으로 풀어버렸다.
굳이 따지자면 데크를 이용한 풀이의 하위호환 비슷한 방법이긴 하다.
사실 이런 풀이는 지양하는 게 맞겠지만(문제를 신기하게 풀면 신기한 대학에 간다는 말을 기억하자), 어쨌든 풀리는 풀이이므로 적어두도록 한다.
가장 먼저 최소 힙과 최대 힙을 만들어 둔다.
리스트를 순회하면서 값을 꺼내서 힙의 값들과 비교하는데, 현재 값이 최소 힙에 c를 더한 것보다 크다면 그 범위는 사일런스가 아니라는 것을 의미한다.
이때, 그 범위를 포함하는 길이 m인 모든 부분수열이 사일런스가 아니므로, 그 부분수열 중 가장 빠른 것과 느린 것의 시작지점을 배열에 표시해둔다.
순회를 완료한 후 표시한 배열에 따라 답을 출력하면 된다.

#!python

from heapq import heappush, heappop

n, m, c = map(int, input().split())
arr = list(map(int, input().split()))

q_min = []
q_max = []
ans = [0 for _ in range(n)]

# 수열 순회
for i, e in enumerate(arr):
    # 최소값에 c를 더한 것보다 큰 동안
    while q_min and e > q_min[0][0] + c:
        temp = heappop(q_min)
        # 거리 m을 벗어났다면 불필요
        if i - temp[1] > m - 1:
            continue
        # m 거리 안에 있으면 현재 숫자 - m + 1에서 시작하는 수열부터 힙에서 꺼낸 숫자로 시작하는 수열은 전부 사일런스가 아님
        ans[max(0, i - m + 1)] += 1
        ans[temp[1] + 1] -= 1

    # 같은 과정을 최대 힙에도 반복
    while q_max and e < -q_max[0][0] - c:
        temp = heappop(q_max)
        if i - temp[1] > m - 1:
            continue
        ans[max(0, i - m + 1)] += 1
        ans[temp[1] + 1] -= 1

    # 마지막에 최소 힙과 최대 힙에 숫자를 넣음
    heappush(q_min, (e, i))
    heappush(q_max, (-e, i))

# 사일런스가 아닌 수열들이 시작하는 부분은 양수, 끝나는 부분은 음수, 합이 0이면 사일런스임을 의미한다
check = 0
none = True
for i, e in enumerate(ans):
    # 수열 전체가 아니라 n-m+1까지만 확인하면 됨
    if i == n - m + 1:
        break
    check += e
    # 합이 0이 아니면 실행하지 않는다
    if check:
        continue
    print(i + 1)
    none = False

# 한번도 숫자를 출력한 적 없다면 NONE 출력
if none:
    print('NONE')

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑