백준 6549 스택을 통해 풀기

목표: 백준 6549 스택을 통해 풀기

환경: mac OS Mojave 10.14, CLion

로직

(왼쪽부터 순서대로)0번 막대기부터 n-1번째까지 체크하면서

stack이 비어있으면 stack에 push하고

stack이 비어있지 않거나, 현재 체크하고 있는 막대기가

stack의 top이 가리키는 막대기보다 더 작으면

while(!st.empty() && arr[i] < arr[st.top()])

pop하여 직사각형의 넓이를 구한다.

0번부터 n-1번까지 모든 막대기를 체크했다면

스택에 막대기가 존재하는지 보고 pop하면서 넓이를 구하고 최대넓이를 갱신한다.

이 문제 풀이법은 오래 잡았으나 풀지 못해서 잘하시는 분들의 로직을 통해 이해했다.

코딩 스킬

  1. 처음 stack에 가상의 막대기 넣기: 너비를 구하는 것이기 때문에 좌우 길이를 구해야한다. 0번째 막대기는 왼쪽 기준이 없으므로, 처음에 -1번짜리 막대기를 넣어줌으로써 0번째 막대기까지 계산하는 로직을 코딩하는데 코드를 줄일 수 있다.

  2. 인덱스만 stack에 push하기: 인덱스만 넣음으로써 높이를 따로 스택에 저장할 필요가 없어진다.

정리

스택 : 이전기록을 기억하기 위해서 사용하는 자료구조

큐 : 병렬로 처리해야할때 사용하는 자료구조

이 문제에서는 너비를 구하는게 포인트였다. 스택을 사용한다면 언제 넣고 언제 빼냐? 그리고 얼마나 넣고 뺄것인가에 대해 고민했다. 이 문제에서는 그 기준이 너비였고, 왼쪽기준과 오른쪽 기준을 정하기 위해서

top에 있는 막대기보다 크다면 push하고, 작다면 pop하여 구할 수 있었다.

스택을 사용했기 때문에 O(N)만에 연산이 가능하게 된 것 같다.

SourceCode