스택/큐
스택
후입선출(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'가 리턴된다.
