[백준 🥇4] 17298번 오큰수 (Python/파이썬)

mingsso·2023년 5월 9일

Algorithm

목록 보기

31/35

1️⃣ 서론

2023 LG전자 코테 2번 문제와 매우 비슷한 문제
코테 리뷰 면접 준비해야 하는데 바보같이 문제 복기를 안해둬서 큰일났다 싶었는데
자소설 채팅방에 어떤 분이 이 문제랑 비슷했다고 그래서 기억남ㅎ

예전에 한 번 풀어봤던 문제인데 그때도 못풀었었네
어쩐지 코테에서 풀긴 풀었는데 진짜 찝찝하더라니

✨ 문제 링크
https://www.acmicpc.net/problem/17298

2️⃣ 풀이

난 그때 힙을 사용해서 풀었었는데 스택으로 푸는 게 일반적인 것 같다

풀이1 - 스택 사용 (1664ms) -> O(N)

n = int(input())
A = list(map(int, input().split()))

stack = []
answer = [-1] * n

stack.append(0)

for i in range(1, n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)

print(' '.join(map(str, answer)))

현재의 수가 누군가의 오큰수일 수 있다고 생각하자 -> 누군가의 오큰수에서 '누군가'들을 스택에 넣어두면 좋을 것이다 -> 여기서 '누군가'는 오큰수를 아직 못찾은 수가 된다

추후에 업데이트하기 위해 스택에 원소값이 아닌 원소의 인덱스를 넣어준다

A가 [3, 5, 2, 7] 일 때,
n=1) 스택에는 0이 들어있으므로 A[1]과 A[0]을 비교한다 -> A[1]이 더 크기 때문에 0이 스택에서 제거되고 answer[0] = 5가 된다 stack = [1]

n=2) 스택에는 1이 들어있으므로 A[2]와 A[1]을 비교한다 -> A[1]이 더 크기 때문에 스택은 그대로다 stack = [1, 2]

n=3) 스택에는 1, 2가 들어있으므로 2부터 비교를 시작한다
A[2]와 A[3]을 비교한다 -> A[3]이 더 크기 때문에 2가 스택에서 제거되고 answer[2] = 7이 된다 stack = [1]
A[1]과 A[3]을 비교한다 -> A[3]이 더 크기 때문에 1이 스택에서 제거되고 answer[1] = 7이 된다 stack = [3]

n=4) 반복문이 종료된다
answer의 초기값은 -1이기 때문에 문제 없다

모든 원소가 스택에 push가 한번씩 되고, pop이 한번씩 되기 때문에 O(N)의 시간 복잡도를 가진다

풀이2 - 우선순위 큐 사용 (2928ms) -> O(NlgN)

import heapq

n = int(input())
A = list(map(int, input().split()))

minHeap = []
answer = [-1] * n

for i in range(n):
    if len(minHeap) == 0:
        heapq.heappush(minHeap, [A[i], i])
        continue

    top = minHeap[0]
    if A[i] <= top[0]:
        heapq.heappush(minHeap, [A[i], i])
    else:
        while minHeap and minHeap[0][0] < A[i]:
            val, idx = heapq.heappop(minHeap)
            answer[idx] = A[i]
        heapq.heappush(minHeap, [A[i], i])

print(' '.join(map(str, answer)))

우선순위 큐를 사용한 풀이도 위의 스택을 이용한 풀이와 비슷하다

이것도 A가 [3, 5, 2, 7] 일 때를 예시로 들어보면,
n=0) minHeap = [[3, 0]]

n=1) top은 [3, 0]이 되고, 5와 3을 비교한다 -> 5가 더 크기 때문에 [3, 0]을 힙에서 제거해주고, answer[0] = 5가 된다 minHeap = [[5, 1]]

n=2) top은 [5, 1]이 되고, 5와 2를 비교한다 -> 5가 더 크기 때문에 [2, 2]를 힙에 추가해준다 minHeap = [[2, 2], [5, 1]]

n=3) top은 [2, 2]가 되고, 7와 2를 비교한다 -> 7이 더 크기 때문에 [2, 2]를 힙에서 제거해주고, answer[2] = 7이 된다
이제 [5, 1]을 비교해줘야 하므로, minHeap[0][0] < A[i]을 top[0] < A[i]으로 쓰면 안된다! 첨에 이거 헷갈림
7과 5를 비교한다 -> 7이 더 크기 때문에 [5, 1]을 힙에서 제거해주고, answer[1] = 7이 된다
minHeap = [[7, 3]]

여기서 고민해볼 점은 왜 우선순위 큐를 사용하냐는 것인데,
minHeap이 만약 [[2, 2], [8, 1]]이고, A[i]가 7이었을 경우 우선순위 큐를 쓰지 않으면 8과 7을 비교하게 되므로 [2, 2]는 검사하지 못하게 된다

그니까 현재의 수가 누군가의 오큰수가 될 수도 있는 건데, 오큰수를 아직 못찾은 수 중 작은 수가 현재의 수가 오큰수일 확률이 높다. 만약 오큰수를 아직 못찾은 수를 수의 크기에 상관없이 검사하려고 하면 아직 못찾은 수 전체를 검사해야할 것이다..

힙에서 원소의 추가할 때와 삭제할 때의 시간복잡도는 O(lgN)이다
스택으로 풀 때와 마찬가지로 모든 원소가 힙에 한번씩 추가되고 삭제되기 때문에 O(NlgN)의 시간 복잡도를 가진다

풀이3 - 이중 for문 사용 (시간초과) -> O(N^2)

이 풀이는 무조건 시간초과가 뜨는 풀이다
하지만 앞의 두 풀이가 얼마나 효율적인지 알기 위해 무식하게 풀어보았다

n = int(input())
A = list(map(int, input().split()))

answer = [-1] * n

for i in range(n):
    for j in range(i+1, n):
        if A[i] < A[j]:
            answer[i] = A[j]
            break

print(' '.join(map(str, answer)))