📶 백준 17608번 : 막대기 (Stack 활용)
🧐 문제 해석
- N개의 막대기 높이가 왼쪽에서 오른쪽 방향으로 입력된다.
🎯 목표:
오른쪽 끝에서 왼쪽을 바라보앗을대 보이는 막대기의 개수를 출력해라
🔍 핵심 아이디어 및 자료구조 & 알고리즘
💭 아이디어
오른쪽에서 봤을 때 보이는 개수를 출력해야 하지만, 애초에 입력을 1개씩 받아야 하기 때문에 입력과 동시에 해당 입력값에 대한 동작을 처리하는 것이 효율적이라고 생각한다.
🤖 자료구조 & 알고리즘
하나의 원소씩 입력을 받을것이며 순차적인 비교 과정과 비교에 대한 처리로
값에 대한 유지/추가/삭제가 용이 해야 하므로 스택 자료구조를 사용한다.
⚙️ 코드 설계 포인트
while(stick and stick[-1]<=num):
stick.pop()
stick.append(num)🔑 새로 들어오는 값의 높이
- 새로운 높이가 너무 높은 값이 들어오면 기존에 더 작은 길이의 높이는 보이지 않는다.
- 단순히 바로 전 막대기만 영향을 받는 것이 아니다.
- n번째까지 내림차순으로 길이가 들어오더라도 마지막 한개의 길이가 길다면 결국 1개밖에 안보인다.
💯 정답 코드
import sys
input = sys.stdin.readline
stick = []
n = int(input())
for i in range(n):
if i == 0 :
stick.append(int(input()))
continue
num = int(input())
while(stick and stick[-1]<=num):
stick.pop()
stick.append(num)
print(len(stick))
💭 생각
⁉️ 방향
입력을 받는 순서대로 판단을 해서 스택에 넣어야 하는지(Left to Right),
다 넣어 놓고 하나씩 빼내면서 판단해야 하는지(Right to Left) 를 고민했다.
- 일단 입력을 하나 하나 받는 상황에서 다 넣어놓고 다시 검사를 하는건 메모리 낭비인 것 같았다.
- 맨 오른쪽 앞 막대기를 기준으로 더 높으면 조건을 만족시킬 수 있다 생각했는데 만약 더 큰 길이가 오른쪽에 있다면 아무리 특정 노드가 기준보다 높더라도 가려질 수 있다.
✔️ 결론
스택으로 구현해서 입력할때마다 모든 원소들을 고려하자
새로 입력 받는 막대기보다 짧다면 전부 pop해줘야 한다.
