스택/큐 문제풀이

자몽·2021년 8월 17일
1

알고리즘

목록 보기
10/31
post-thumbnail

스택/큐

스택

후입선출(LIFO) => 마지막에 들어온 데이터가 가장 먼저 나감

JS에서, push, pop을 통해 사용할 수 있다.

활용

웹 브라우저 방문 기록
실행 취소
괄호 검사
후위표기법 계산


선입선출(FIFO) => 먼저 들어온 데이터가 가장 먼저 나감

JS에서, push, shift을 통해 사용할 수 있다.

활용

작업 예약
대기열


Largest Rectangle [HackerRank]

문제

https://www.hackerrank.com/challenges/largest-rectangle/problem?isFullScreen=true
한정된 범위 내에서 만들 수 있는 가장 큰 사각형을 구하는 문제이다.

코드

function largestRectangle(heights) {
    let result = 0;
    let stack = []

    heights.map((h, index) => {
      
      	// 스택이 비어있다면 [h, index]의 배열 형태로 stack에 push한다.
        if (stack.length === 0) {
            stack.push([h, index])
        } else {
          	// 그렇지 않다면,
          	// 가로 길이를 인덱스로 설정하고,
            let width = index;
          	// 현재 빌딩보다 자신의 앞 빌딩 크기가 더 크다면, 
            while (stack.length !== 0 && h < stack[stack.length - 1][0]) {
              
              	// 앞 빌딩을 stack에서 빼와, value에 저장한다.(현재 빌딩을 아직 stack에 넣지 않았기 때문)
                let value = stack.pop();
               	// 가로 길이는 앞 빌딩의 index가 되고,
                width = value[1];
              	// 그 결과 사각형의 넓이는 앞 빌딩의 높이 * (현재 빌딩까지 index- 앞 빌딩) 이 된다.
                let size = value[0] * (index - value[1])
                // 만약, 더 큰값이 들어오면 result 교체
                if (result < size) result = size
            }
          	// 현재 결과를 width 정보와 함께 stack에 넣어준다.
            stack.push([h, width])
        }
    })
	// 스택을 순회하면서, 더 큰 사각형을 만들 수 있다면, 찾아준다.
    stack.map(s => {
        let size = s[0] * (heights.length - s[1])
        if (result < size) result = size
    })
    return result;

}

문제 풀이

[1,3,2,3,4]가 input으로 받는 height라고 하자.

그러면 그림은 다음과 같이 그려진다.

그림에서 볼 수 있는 회색부분이 만들 수 있는 최대 사각형의 넓이이다.

이 문제를 풀 때의 가장 핵심은 아무리 높은 빌딩이여도, 다음 빌딩의 높이가 그보다 낮으면 아무 소용이 없다는 것이다.

따라서 다음 그림과 같이 이미 지나간, 높은 빌딩들의 높이는

아무리 높아도 그 다음 빌딩에 의해 운명이 정해진다.

이 부분에 대한 아이디어는 코드에서 다음과 같은 부분을 맡고 있다.

while (stack.length !== 0 && h < stack[stack.length - 1][0]) {
              
  // 앞 빌딩을 stack에서 빼와, value에 저장한다.(현재 빌딩을 아직 stack에 넣지 않았기 때문)
  let value = stack.pop();
  // 가로 길이는 앞 빌딩의 index가 되고,
  width = value[1];
  // 그 결과 사각형의 넓이는 앞 빌딩의 높이 * (현재 빌딩까지 index- 앞 빌딩) 이 된다.
  let size = value[0] * (index - value[1])
  // 만약, 더 큰값이 들어오면 result 교체
  if (result < size) result = size
}

순차적으로 stack에 어떤 값이 들어가는지 콘솔창을 통해 확인해 본 결과 다음과 같은 결과가 나왔다.

[1,0]이 처음에 stack에 들어가고 그 다음 [4,1]까지 순차적으로 stack에 저장된다.

하지만 [2,1]을 만나면 2<4가 되기 때문에, [4,1]을 pop 시키고, [2,1]을 넣어준다.

이후에는 이전 빌딩이 더 큰 경우가 없기 때문에 순차적으로, [3,3] -> [4,4]가 stack에 들어가게 된다.

따라서, 최종적으로 stack에는 [1,0], [2,1], [3,3], [4,4]가 들어가게 되며, 다음과 같은 그림이 그려진다.

앞 과정을 정상적으로 이해했다면, 여기서부터 한 가지 고민에 빠지게 된다.
"어떻게 최대 넓이를 구하지?" 라고 말이다.

해결책은 간단하다.
스택을 순회하면서 let size = s[0] * (heights.length - s[1])다음과 같이 size를 만들어주고 result 값을 지속적으로 업데이트 해주는 것이다.

괄호 [Baekjoon]

문제

https://www.acmicpc.net/problem/9012

코드

const bracket = (arr) => {
  	// stay에는 ')'값만 들어간다.
    let stay = [];
    while (arr.length > 0) {
        let temp = arr.pop();
      	// temp가 '('이고, stay.pop이 ')'인 경우 참
        if (temp === '(') {
            if (stay.pop() !== ')') {
                return 'NO';
            }
        } else {
            stay.push(temp)
        }
    }
  	// arr과 stay가 모두 빈 경우, return 'YES'
    if (arr.length === 0 && stay.length === 0) {
        return 'YES';
    }
    return 'NO';
}

function main() {
    let fs = require('fs');
    let input = fs.readFileSync('/dev/stdin').toString().split('\n');

    const caseCount = Number(input[0]);
    for (let i = 1; i <= caseCount; i += 1) {
        let cases = input[i];
        let arr = []
        for (let i = 0; i < cases.length; i++) {
            arr.push(cases[i])
        }
        console.log(bracket(arr))
    }
}
main()

문제 풀이

입력받은 값들은 모두 arr 배열에 들어간다.
그러한 상태에서 arr 배열의 값이 모두 사라질 때까지 while문을 돌린다.

while 문에서는, 젤 마지막 값을 하나씩 뽑아서,
')'를 만나면 stay에 해당 값을 넣어주고,
'('를 만나면 stay에 ')'가 있는 지 확인 후, 결과를 return 한다.

따라셔, ')'가 arr에 남아있는데, stay에 값이 더 이상 없는 경우 'NO'가 리턴되고,
arr과 stay 배열이 모두 비워졌다면 'YES'가 리턴된다.

profile
꾸준하게 공부하기

0개의 댓글