https://www.acmicpc.net/problem/2493
1. 단순 탐색 풀이 - O(n^2)
시간복잡도 O(n^2)를 가지는 모든 요소를 탐색하는 방식으로 풀이했다. 당연히, 시간초과로 실패했다.
N = int(input().strip())
heights = list(map(int, input().strip().split()))
def get_answer():
answer = [0 for _ in range(N)]
for i in range(len(heights), 0, -1):
if i == 1:
break
current_top = heights[i - 1]
for j in range(i - 1, 0, -1):
left_top = heights[j - 1]
if left_top >= current_top:
answer[i - 1] = j
break
print(" ".join(map(str, answer)))
get_answer()
2. 스택 이용한 풀이 - 최악 O(n^2), 최선 O(n)
스택을 사용하면 각 요소를 한 번만 처리(삽입/삭제)하게 되어, 이미 검사한 요소들을 재검사하지 않아도 된다.
일반적으로 스택 기반 알고리즘에서는 리스트를 한 번 순회하며, 현재 요소보다 작은(또는 큰) 후보들은 스택에서 제거하는 식으로 진행하여, 각 요소가 스택에 한 번 push되고 최대 한 번 pop되도록 한다.
최악의 경우:
예를 들어, 만약 리스트가 내림차순 정렬되어 있다면, 각 요소마다 내부 for 루프가 거의 전체 남은 요소를 검사하게 된다.
따라서 전체 연산 횟수는 약 n+(n−1)+(n−2)+…+1=O(n^2)가 된다.
N = int(input().strip())
heights = list(map(int, input().strip().split()))
def get_answer():
answer = [0 for _ in range(N)]
while heights:
height = heights.pop()
for i in range(len(heights) - 1, -1, -1):
if height < heights[i]:
answer[len(heights)] = i + 1
break
print(" ".join(map(str, answer)))
get_answer()
3. 스택 이용한 풀이 - 최적화 O(n)
N = int(input().strip())
heights = list(map(int, input().strip().split()))
def get_answer():
answer = [0 for _ in range(N)]
stack = [] # 인덱스 저장
for i in range(len(heights)):
height = heights[i]
# 스택에 있는 인덱스의 높이가 현재보다 작으면, 이들은 현재 탑의 신호를 받을 수 없음
while stack and heights[stack[-1]] < height:
stack.pop()
# 스택이 남아 있으면, 스택의 최상단 인덱스가 현재 탑의 신호를 수신하는 탑이다
if stack:
answer[i] = stack[-1] + 1
else:
answer[i] = 0
stack.append(i) # 현재 탑 인덱스 추가
print(" ".join(map(str, answer)))
get_answer()