[JavaScript] 백준 2304 창고 다각형 (JS)

창고 다각형

📚 문제 설명

N 개의 기둥이 있고 그 막대기 위에 아래 조건으로 지붕을 만드려고 한다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

👨🏻‍💻 풀이 과정

이 문제를 보면 지붕으로 쓰이는 높이의 기둥을 보면 가장 높은 기둥을 기준으로 2개의 영역이 나누어 지는 것을 알 수 있다.
가장 높은 기둥 기준으로 왼쪽은 오름차순으로, 오른쪽에는 내림차순으로 높이를 나열해야 한다.

그런데 여기서 오름차순의 경우 무조건 시작점을 기준으로 Pop 되는 요소 없이 오름차순으로 정렬해야한다.
그럼 해당 오름차순 스택의 마지막에는 가장 높은 기둥이 들어오게 된다.

반면, 내림차순의 경우 일전에 했던 Monotinic Stack(단조 스택) 을 이용하여 내림차순을 만들어 주면 될 것이고,
해당 스택의 가장 아래에는 가장 높은 기둥이 있을 것이다.

스택 생성

    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let StackUp = [];
    let StackDown = [];
    input = input.map(v => v.split(' ').map(Number));
	// 기둥의 가로축 기준 위치로 정렬
    input.sort((a, b) => a[0] - b[0]);

    for (let i = 0; i < input.length; i++) {
      	// 오름차순 정렬
        if (StackUp.length) {
            if (StackUp[StackUp.length - 1][1] < input[i][1]) {
                StackUp.push(input[i]);
            }
        } else {
            StackUp.push(input[i]);
        }
		// 내림차순 정렬
        while (StackDown.length) {
            if (StackDown[StackDown.length - 1][1] < input[i][1]) {
                StackDown.pop();
            }else break;
        }
        StackDown.push(input[i]);
    }

그 후에 각각의 스택을 확인하며, 직사각형의 넓이를 계산한다.
가로 길이 : 스택[i + 1][0] - 스택[i][0]
높이 : 기둥의 높이

건물의 넓이 계산

    let answer = 0;
	// 가장 높은 기둥 기준 왼쪽 부분 넓이 계산
    for (let i = 0; i < StackUp.length - 1; i++) {
        answer += (StackUp[i + 1][0] - StackUp[i][0]) * StackUp[i][1];
    }
	// 가장 높은 기둥 기준 오른쪽 부분 넓이 계산
    for (let i = 0; i < StackDown.length - 1; i++) {
        answer += (StackDown[i + 1][0] - StackDown[i][0]) * StackDown[i + 1][1];
    }
	// 가장 높은 기둥의 넓이만큼 더해줘야함
	answer += StackDown[0][1];

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    let StackUp = [];
    let StackDown = [];
	let answer = 0;

    input = input.map(v => v.split(' ').map(Number));
	// 기둥의 가로축 기준 위치로 정렬
    input.sort((a, b) => a[0] - b[0]);

    for (let i = 0; i < input.length; i++) {
      	// 오름차순 정렬
        if (StackUp.length) {
            if (StackUp[StackUp.length - 1][1] < input[i][1]) {
                StackUp.push(input[i]);
            }
        } else {
            StackUp.push(input[i]);
        }
		// 내림차순 정렬
        while (StackDown.length) {
            if (StackDown[StackDown.length - 1][1] < input[i][1]) {
                StackDown.pop();
            }else break;
        }
        StackDown.push(input[i]);
    }
    
	// 가장 높은 기둥 기준 왼쪽 부분 넓이 계산
    for (let i = 0; i < StackUp.length - 1; i++) {
        answer += (StackUp[i + 1][0] - StackUp[i][0]) * StackUp[i][1];
    }
	// 가장 높은 기둥 기준 오른쪽 부분 넓이 계산
    for (let i = 0; i < StackDown.length - 1; i++) {
        answer += (StackDown[i + 1][0] - StackDown[i][0]) * StackDown[i + 1][1];
    }
	// 가장 높은 기둥의 넓이만큼 더해줘야함
	answer += StackDown[0][1];
    console.log(answer);

🧐 후기

처음에는 가장 높은 기둥을 따로 찾고 그 기둥을 기준으로 왼쪽과 오른쪽을 따로 계산하려 했는데 그렇게 하면 너무 복잡한 것 같다고 느꼈다.
따라서 반복문 1개를 돌며 스택 2개를 만들어서 사용하는 풀이를 생각하게 되었다.