백준 정렬 2493번 - 탑

안녕하세요. GDSC 안드로이드 멤버 한윤재입니다.
백준 스택 2493번 문제를 풀었습니다.

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

풀이

처음에는 모든 빌딩을 스택에 넣어서 비교하는 코드를 작성했으나, 시간 초과가 발생해 최고점을 스택에 입력해 비교 횟수를 줄였습니다.

다음은 핵심코드입니다.

n = int(sys.stdin.readline())
tower = map(int,(sys.stdin.readline().rstrip().split()))
stack =[]
result = [0]*n
for idx, i in enumerate(tower) :
    #스택이 비어있으면 0 입력
    result[idx] = 0
    #루프에서 최고점인 탑만 입력
    while len(stack) :
        if peek(stack) > i :
            result[idx] = stack[-1][1]
            break
        else :
            pop(stack)
    push(stack, [i, idx+1])

#리스트를 합쳐서 출력
print(" ".join(map(str, result)))

스택으로 분류된 문제를 풀면서 push, peek, pop 함수를 만들어 놓고 문제를 풀었는데, 굳이 함수를 지정하지 않아도 간결한 코드로 문제를 풀 수 있을 것 같습니다.

마무리

시간초과가 난 코드는 작성하면서도 스택 개념을 잘 활용하지 못하는 느낌이 있었는데, 개선한 코드를 보면 확실히 스택의 특성을 잘 살려 문제를 해결한 것이 보입니다.

참고자료

알고리즘 스터디 스택-2493번

스택 알고리즘 2493번 풀이

백준 정렬 2493번 - 탑

풀이

마무리