첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)
두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.
따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.
출력
2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.
빗물이 전혀 고이지 않을 경우 0을 출력하여라.
예제 입력 1복사
4 4 3 0 1 4
예제 출력 1복사
5
예제 입력 2복사
4 8 3 1 2 3 4 1 1 2
예제 출력 2복사
5
예제 입력 3복사
3 5 0 0 0 2 0
예제 출력 3복사
0
힌트
힌트 1:
힌트 2:
힌트 3:
풀면서...
전에 C++로 풀어본 적이 있는 문제라서 쉽게 생각하고 풀었는데요. 원래는 스택만으로 풀었다가 큐로 풀 수 있을거 같은 느낌이들어서 큐로 풀었습니다.(결론은 사실상 똑같은...)
그런데 바로 틀렸다는 메세지가...
그래서 전에 짰던 방식대로 스택을 사용했지만 똑같은 결과가 나오네요..ㅠ
그래서 코드를 확인해 보니...
하.. 아직 JS가 익숙하지 않아서 콘솔로 입력 확인해본다고 log찍어 보고 지우질 않았네요..
무튼 사실상 똑같은 2개의 코드라는 결과를 내며.... 풀이 시작합니다.
풀이
1. forEach는 각 0번 인덱스의 블록부터 W-1번째 블록까지 하나씩 반복하는 구문이다.
2. 기본적으로 모든 블록을 stack에 넣는 작업을 한다고 생각한다.
3. h는 현재 블록을 보기 전에 가장 큰 블록이다. 따라서 h와 같거나 큰 블록이 나오면 현재까지 stack에 넣은 블록들과 h와의 차이만큼을 sum에 더한다. stack에는 h보다 큰 블록이 들어가 있지 않아 h에서 각 값들을 빼준다.
4. forEach문 반복이 끝났을 때에도 예를 들면 5 2 4 1 3 같은 경우에는 모든 원소가 stack안에 들어가 있다. 5보다 큰 블록이 없기 때문이다.
5. 따라서 이번에는 반대로 남은 원소들을 가지고 오른쪽에서 왼쪽으로 순회하며 while문을 반복한다.
6. 4번의 예의 경우 3을 기준인 h로 잡고 원소를 하나씩 빼면서 h와의 차를 sum에 더해주고, 꺼낸 원소가 h와 같거나 큰경우(예에서는 3번째 4) h로 바꿔준다. 이렇게 마지막 5를 만날 때까지 반복을 돌리고 sum을 출력해준다.
※ 코드 1번 2번 모두 같은 개념입니다.
코드
// 1번( stack만 이용)
const input = require("fs").readFileSync("./dev/stdin").toString().trim().split("\n");
const line = input[0].trim().split(' ');
const H = line[0], W = line[1];
const block = input[1].toString().trim().split(' ').map(function(a){return parseInt(a)});
let stack = [];
let sum=0;
let h; // 기준 높이
block.forEach(function(b, i){
if(stack.length==0){
stack.push(b);
h = b;
return;
}
if(h<= b){ // 기준 높이보다 높거나 같은게 나왔을 때.
// 기준 vs 현재
while(stack.length>0){
let top = stack.pop();
sum += h-top;
}
h = b;
}
stack.push(b);
});
if(stack.length>0){
h = stack.pop();
while(stack.length>0){
let top = stack.pop();
if(h<=top){
h = top;
continue;
}
sum += h-top;
}
}
console.log(sum);
// 2번( deque 이용)
const input = require("fs").readFileSync("./dev/stdin").toString().trim().split("\n");
const line = input[0].trim().split(' ');
const H = line[0], W = line[1];
const block = input[1].toString().trim().split(' ').map(function(a){return parseInt(a)});
let deque = [];
let sum=0;
block.forEach(function(b, i){
if(deque.length==0){
deque.push(b);
return;
}
if(deque[0]<= b){
let h=Math.min(deque[0], b);
while(deque.length>0){
let dequeue = deque.shift();
sum+=h-dequeue;
}
}
deque.push(b);
});
if(deque.length>0){
let h = deque.pop();
while(deque.length>0){
let pop = deque.pop();
if(pop<h){
sum+=h-pop;
}else{
h = pop;
}
}
}
console.log(sum);
댓글