[PYTHON] 백준 17608

성능 요약

메모리: 122492 KB, 시간: 400 ms

분류

자료 구조, 구현, 스택

문제 설명

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

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

입력

첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다.

출력

오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다.

---

아이디어, 문제풀이

• 오른쪽에서 보기때문에, 마지막에 입력받은 값은 맨오른쪽에 위치
• 오른쪽에 위치한 것부터 판단할것이기 때문에, 스택을 활용해야 한다.
• 마지막에 입력한값을 맨 처음 출력하는 방식 (후입선출)

---

TROUBLE SHOOTING

• 일단 값들을 배열에 넣고, max() 를 활용해 최대값을 구하게 되면, 시간초과가 나온다ㅋㅋ

  elif n_list[i] > max(result):
          result.append(n_list[i])

  생각해보면 당연한거 였는데, 최대값을 찾기 위해 매번 반복해서 전체 배열을 순회탐색(전체탐색) 하기 때문이다. 실제로 이 코드에서 시간복잡도는 최악의 경우 O(n^2) 이된다.
  따라서, 아래 코드처럼 현재까지 찾은 최대값을 변수에 저장하는 식으로 풀이를 하게되면, 시간복잡도를 줄일 수 있게된다.

  if n_list[i] > max_result:
          result.append(n_list[i])
          max_result = n_list[i]

---

코드

#https://www.acmicpc.net/problem/17608
#막대기
#17608

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
n_list = deque()
for i in range(n):
    a = int(input())
    n_list.appendleft(a)

# print(n_list)

result = []
max_result = 0

for i in range(n):
    # n_list[i] = int(input())
    # if len(result) == 0:
    #     result.append(n_list[i])

    # elif n_list[i] > max(result):
    #     result.append(n_list[i])

    if n_list[i] > max_result:
        result.append(n_list[i])
        max_result = n_list[i]
    

# print(result)

print(len(result))