김낭만

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

백준(BOJ) 17299 오등큰수 파이썬(Python)

문제 링크

17298번(오큰수)과 대동소이한 스택 문제.
이 문제를 풀고 나서 보니 오큰수 문제를 푼 게 2년 전이던데, 사실 이름이 너무 특이해서 예전에 오큰수라는 문제가 있었던 걸 어렴풋이 기억은 하고 있었다.
그래서 그런지 아니면 문제가 쉬워서 그런지 바로 스택을 떠올릴 수 있었다.
오등큰수는 풀이하자면 아마 오른쪽에 있는 등장한 빈도가 더 큰 수 정도 될 것 같다.
중요한 부분은 자신보다 오른쪽에 있는 수 중 가장 왼쪽에 있는 숫자만 알면 된다는 점인데, “가장” 왼쪽이라는 것(즉 스택의 탑을 의미한다), 그리고 순회하며 답을 구해야 한다는 것에서 스택 문제임을 알 수 있다.
일단 수열을 뒤집어서, 즉 우측부터 순회하면 된다.
그 이후는 예시를 가지고 직접 생각해보면서 스택이 어떻게 변화하는지 보면 된다.
먼저 스택의 탑(예를 들어 빈도 2)보다 빈도가 작은 수(예를 들어 빈도 1)가 들어온다면, 당연히 스택의 탑이 현재 수의 오등큰수일 것이다.
만약 스택의 탑보다 빈도가 크거나 같은 수(예를 들어 빈도 3)가 들어온다면, 스택의 탑은 수열의 남은 부분(좌측)의 오등큰수가 절대 될 수 없다.
왜냐하면 나중에 들어올 어떤 수 A[i]가 그 스택의 탑보다 빈도가 낮다면(예를 들어 빈도 1), 당연히 지금 들어온 수보다도 빈도가 낮을 것이기 때문이다(스택의 탑보다 현재 수가 빈도가 크거나 같으므로).
따라서 현재 탑은 필요가 없으므로 팝하면 된다.
이렇게 팝하는 과정을 반복하다가 탑의 빈도가 현재 숫자의 빈도보다 커진다면, 그 숫자가 오등큰수일 것이다.
이 과정을 끝낸 후, 현재 숫자가 다른 숫자의 오등큰수일 수 있으므로 현재 숫자를 스택에 추가한다.
그 외에는 스택이 비는 경우는 -1을 출력하므로 이를 예외처리 해주면 된다.
이렇게 구해진 오등큰수 목록은 우측부터 구해진 것이므로 뒤집어서 출력해주면 된다.

#!python

n = int(input())
# 수열 A
arr = list(map(int, input().split()))
# f(Ai)
f = [0 for _ in range(1_000_001)]
# 스택
stack = [-1]
# 정답 리스트
ans = []

# f값(빈도)을 구해준다
for e in arr:
    f[e] += 1

# 리스트를 역순으로 순회하면서
# 탑의 빈도가 현재 원소의 빈도보다 낮거나 같은 동안 전부 팝하고
# 탑의 빈도가 현재 원소의 빈도보다 높아지면 그 숫자가 답이 된다
# 이후에 스택에 현재 원소를 넣는다
for e in reversed(arr):
    while f[stack[-1]] <= f[e]:
        if stack[-1] == -1:
            break
        stack.pop()

    ans.append(stack[-1])
    stack.append(e)

# ans는 뒤에서부터 구해졌으므로 뒤집어야 한다
print(*reversed(ans))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑