[백준 2493] 탑 - Python(스택)

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()