[백준 17608] 막대기(Feat.Python)

문제

아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다.

 

N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 프로그램을 작성하려고 한다.

 

 

풀이

• 본인은 처음 이 문제를 보자마자 for문을 통해 맨 처음 입력 받는 N-1부터 0번까지 거꾸로 for문을 돌려서 구현을 성공했었으나, reversed라는 배열의 순서를 거꾸로 바꾸어주는 함수를 사용 + stack구조를 응용해보고자 하였다

import sys

input = sys.stdin.readline
N = int(input())
li = [int(input()) for _ in range(N)]

ans = [0]
for i in reversed(li):
    if ans[len(ans)-1] < i:
        ans.append(i)

print(len(ans)-1)

 

• ans 라는 배열(이하 스택) 안에 0 하나 들어있고 li라는 배열에는 입력 받는 숫자들이 있다.
• ans의 top 부분, (맨 처음에는  0) 보다 크면 스택으로 push, 그렇치 않으면 무시하고 넘어간다.
• 배열을 다 돌았을 때, stack의 길이에서 하나를 빼준다.
• input = sys.stdin.readline 이걸 해주지 않으면 시간초과가 나온다.