[백준] 17608번: 막대기

막대기

문제

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

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

입력

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

출력

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

 

해당 문제는 Stack을 통해 문제를 접근해야한다. 해야되지만, 나는 그냥 풀었다. 이전에 프로그래머스 문제에서 봤었던 문제이기도 하고 좀 유명(?)한 문제인 것 같아서 바로 풀 수 있었다.

 

문제 접근은 간단하다. 막대기들의 높이를 배열에 담고 0번 index부터가 아닌 마지막 인덱스부터 0번까지 역순으로 접근하며 막대기의 높이를 비교하면서 보이는 막대기를 count하는 방법으로 풀었다. 아마 이 방법이 가장 접근하기 쉬운 해결방법이지 않을까 싶다. 아래는 문제의 코드이다.

 

"""
백준 알고리즘 17608번: 막대기
https://www.acmicpc.net/problem/17608
"""
import sys

def calc(height):
    # 가장 오른쪽에서 부터 시작함으로 가장 높은 탑의 높이를 저장
    max = height[-1]
    cnt = 1 #가장 오른쪽 타워는 보임으로 1부터 카운트

    # 0번 막대기 부터 마지막 막대기를 제외한 막대기 까지 역순으로 참조
    for i in range(len(height)-1,-1 , -1):
        # 참조한 막대기의 높이가 가장 높은 막대기 보다 높이가 크면 카운트
        if height[i] > max:
            cnt += 1
            max = height[i]
    return cnt

def main():
    n = sys.stdin.readline()
    n = int(n)

    height = []
    for i in range(n):
        height.append(int(sys.stdin.readline()))
    print(calc(height))

if __name__ == '__main__':
    main()

주석에서 처럼 0번부터 마지막 막대기를 제외한 막대기를 for반복을 통해 비교해 나간다. 가장 큰 높이를 가진 막대기의 높이를 max라하고 그 높이보다 높다면 카운트 하는 방법으로 해결하였다.

 

아마 스택으로 푼다면 그냥 입력 순서대로 스택에 막대기의 높이를 삽입하고 하나씩 꺼내면서 높이를 비교하는거 같은데 사실상 스택으로 푸나 위 코드처럼 for를 통해 역순으로 접근하거나 똑같지 않나 싶다.