[백준] 막대기(python)

백준, 막대기

TL;DR

• 스택(Stack)

문제 요약

1. 높이가 서로 다른(같을 수 있음) 막대기를 일렬로 세운 후 오른쪽에서 봤을 때 보이는 막대기의 개수를 알아내는 프로그램을 작성하라.

 

- 일렬로 세운 막대기를 가장 오른쪽에서 봤을 때 보이는 막대기의 수를 반환하면 된다.

- 가장 오른쪽에 있는 막대기보다 크기가 작은 막대기들은 보이지 않을 것이고, 큰 막대기들이 보일 것이다.

입출력 형태

그림

 

입출력 예시

 

- 주어진 예시에서 1번 막대기는 2번 막대기에 가려지고 4, 5번 막대기는 6번 막대기에 의해 가려져서 보이지 않는다. 따라서 보이는 막대기는 2, 3, 6번 막대기가 되어 총 3개가 된다.

풀이

막대기의 길이를 스택에 입력받는다. 가장 마지막에 들어오는 원소가 스택의 최상단에 위치할 것이다. 스택에서 하나씩 막대기의 길이를 pop 하며 보이는 막대기를 판별하면 될 것 같다.

import sys

n = int(sys.stdin.readline())
stack = [int(item) for item in sys.stdin.read().split()]

bars, _max = set(), -1

while stack:
    top = stack.pop()
    _max = max(_max, top)

    if top >= _max:
        bars.add(top)

print(len(bars))

 

- 보이는 막대를 저장하기 위해 set인 bars를, 가장 큰 길이를 갖고 있는 막대기의 길이를 갱신하기 위해 _max 변수를 할당하였다.

  - 가장 오른쪽에 있는 막대기의 길이보다 큰 막대기의 수를 세는 경우를 생각할 수 있지만 이 경우에는 동작하지 않는 예시가 있다.

  - 막대기의 순서가 [7, 9, 7, 6, 4, 6]으로 배치되었을 때 가장 오른쪽에 있는 막대기의 길이는 6이다. 앞서 생각한 방법으로 문제를 풀었을 때는 가장 왼쪽에 있는 7도 보이는 막대기로 여겨진다. 하지만 7은 9에 의해서 보이지 않아야 한다.

  - 따라서, 막대기를 스택에서 뽑아낼 때 가장 긴 막대의 길이를 갱신하여 가장 긴 막대의 길이와 비교를 해야 한다. 이 때, _max를 사용한다.

 

- 스택에서 막대기를 하나씩 뽑으며 긴 막대기의 길이를 _max에 갱신한다. 갱신한 이후 뽑아낸 막대기의 길이와 _max를 비교한다. 만약 뽑아낸 막대기의 길이가 _max보다 크거나 같으면 보이는 막대기가 될 수 있다. 이 막대기들을 set에 저장한다.

  - 크거나 같은 조건으로 설정한 이유는 가장 오른쪽 막대기, 즉 가장 처음 뽑아낸 막대기를 포함시키기 위해서이다. 만약 크다는 조건만 설정할 경우 가장 먼저 보이는 오른쪽 막대기가 포함되지 않기 때문에 크거나 같다는 조건으로 구현하였다.

  - 보이는 막대기를 set으로 한 이유는 [1, 1, 1]과 같이 모두 길이가 같은 막대기가 주어졌을 때에 대응하기 위해서이다. 이 경우 답은 1이 되어야 하는데 set으로 하지 않을 경우 3이 되기 때문이다.

 

- 이 과정을 거치면 bars에는 보이는 막대기들이 저장되게 된다. 저장된 막대기의 길이를 출력하면 된다.