BOJ 2493. [Gold5] 탑

[hojongs]

Problem link

https://www.acmicpc.net/problem/2493

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

1
1
0

5
8 9 1 1 1
0 0 2 2 2

a 높이의 탑들이 있고 a+b 높이의 탑이 맨 앞쪽에 있는 입력
역순으로 순회하면 O(N^2)

6
8 1 5 4 7 4
0 1 1 3 1 5

정답이 1 -> 3 -> 1과 같이 감소 후 증가할 수 있는 입력
[8 5]
[8 7 4]
7 높이를 만난 후에는 5 높이는 중요하지 않음

5
8 1 1 8 7
0 1 1 0 4

같은 높이의 탑이 있는 입력
[8]
[8]
이전 8 높이는 중요하지 않음

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

• 좌->우(정방향) 순회
• Monotone stack 활용

Pseudo-code

idea를 수도 코드로 작성해본다

• 코드 주석 참고

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

n = int(readl())
# 크기 비교 필요 -> 정수형 변환
nums = [int(i) for i in readl().rstrip().split()]

def f():
    # 인덱스 출력 필요 -> 인덱스 값 저장 필요
    # Monotone stack. 내림차순 정렬됨
    idx_stack = [0]
    result = ['0'] * n
    for i in range(1, n):
        # stack에서 nums[i]보다 큰 높이 중 가장 작은 높이를 찾음 -> 인덱스 저장
        for k in range(len(idx_stack)-1, -1, -1):
            idx = idx_stack[k]
            if nums[idx] > nums[i]:
                result[i] = str(idx+1)
                break
        # stack에 nums[i]를 넣음 (조건에 따라)
        while len(idx_stack) > 0 and nums[idx_stack[-1]] <= nums[i]:
            idx_stack.pop()
        idx_stack.append(i)
    print(' '.join(result))

f()

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?

[hojongs]

수신 높이를 찾을 떄 단순 순회가 아니라, 바이너리 서치를 활용하면 해당 부분만 O(n) -> O(log(n))로 줄일 수 있을 듯함 (stack의 길이가 n-1일 경우)

10
9 8 7 6 5 4 3 2 8
0 1 2 3 4 5 6 7 1