백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 6549 히스토그램에서 가장 큰 직사각형 [스택]

백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 6549 히스토그램에서 가장 큰 직사각형 [스택]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

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

6549번: 히스토그램에서 가장 큰 직사각형

 

 

 

문제풀이 소감 🧑‍💻

해볼만 한 문제 같아서 덤볐는데, 역시 플레 문제는 다 이유가 있다.

 

도형이 끊기는 경우를 해결하는 것이 관건이였다. 이 문제는 특히 index를 잘 생각해서 계산해야함.

 

 

 

 

요구사항 📋

• 히스토그램에서 가장 넓이가 큰 직사각형을 구하여라.
• 테스트는 0이 나올때까지 계속 주어진다.
• 0이 입력되면 프로그램을 종료한다.

 

 

주의 ❗

중간에 도형이 끊기는 경우도 고려해야함.

 

따라서, 초기 MAX값을 0으로 설정.

 

 

반례

9 3 2 1 0 1 2 3 3 3
0

 

Answer : 9

 

 

3 2 1 2
0

 

Answer : 3

 

 

 

해결 전략 📝

 

각 높이에서 수평선을 쭉 그어 해당하는 넓이를 계산한다.

 

우리가 히스토그램의 넓이를 직관적으로 계산할 때 쓰는 방법을 그대로 적용할 것이다.

 

접근 방법은 스택 끝 값에 담긴 높이가 현재 해당하는 블럭의 높이보다 낮을 때까지 스택에 저장한다.

 

이후, 스택 끝 값에 담긴 높이가 현재 해당하는 블럭의 높이보다 높은 경우 while 문에 들어간다.

 

예시를 보면서 설명하겠다.

 

 

7 2 1 4 5 1 3 3

 

 

 

 

 

처음에는 스택에 담아주기만 한다. 이때까지는 MAX값 계산을 하지 않기 때문에 0으로 유지된다.

 

 

 

 

 

스택에 담긴 값보다 작은 값이 등장 했다.

 

스택에 담긴 값을 pop 하고 MAX 값을 계산해준다.

 

이때 계산된 MAX영역은 0인덱스에 위치한 도형만 계산해서 나온 경우이다.

 

 

 

 

 

스택 끝에 담긴 값보다 크기 때문에 push 만 한다. MAX값은 계산되지 않는다.

 

 

 

 

스택 끝에 담긴 값보다 크기 때문에 push 만 한다. MAX값은 계산되지 않는다.

 

 

 

 

스택 끝에 담긴 값들 보다 작은 경우가 나왔다.

 

스택에 담겨있던 [ 5, 3 ] => [ 4, 2 ] 순으로 pop 되어 나와진다. [ 1, 1 ] 은 높이가 같기 때문에 pop 되지 않는다.

 

각 스택값은 pop되어 MAX 값을 계산하는데 사용된다.

 

이 과정은 stack 끝값이 현재의 block 보다 작거나 같은 값이 나올때까지 진행된다.

 

여기서 주의해야할 점은 stack에 담긴 값들의 갯수에 따라 width를 계산하는 법이 달라진다는 것이다.

 

이게 이 문제에서 핵심이다.

 

스택에 담긴 값이 있다면, pop 하고 남은 스택들 중에서 가장 끝값에 해당하는 index를 현재 인덱스에서 빼준 뒤 또 1을 빼준다. 1을 또 빼주는 이유는 길이를 맞춰주기 위함이다.

 

예를 들어 pop 된 값이 [ 5, 3 ] 이라면 이 시점에서 스택에 담겨있는 값들 [ [ 1, 1 ] , [ 4 , 2 ] ] 들 중 가장 끝 값 [ 4, 2 ] 에서 4의 index 값 2를 빼주는 것이다.

 

처음에 이 부분을 생각해내기가 힘들었다.

 

 

이렇게 연산하는 이유는

 

 

이 파란 부분을 계산하기 위함이다.

 

현재 인덱스에 해당하는 4에서 스택 끝값 2를 뺀 뒤 1을 빼주면 1만 남는다.

 

이 값은 5와 곱해줘야 할 길이를 뜻하고 이 연산을 하게되면 MAX값은 5로 초기화된다.

 

 

 

 

 

 

다음은 [ 4, 2 ] 값이 pop 되어지는 경우이다.

 

현재 인덱스는 4로 동일하고 이 값에서 스택 끝값 1의 인덱스 1과 또 1을 빼주면 2가 나온다.

 

이 값은 도형위치 2의 높이에 해당하는 4와 곱해줄 길이인데, 위 그림의 파란부분에 해당하는 넓이를 구해주는 과정이다.

 

이 연산을 수행하게 되면 MAX값은 8로 초기화되며, 이 값이 최종적으로 가장 큰 넓이에 해당한다.

 

 

만약, pop을 하고 스택에 담긴 값이 없다면 width는 현재 해당하는 인덱스 값이 된다.

 

 

 

 

 

 

스택 끝에 담긴 값보다 크기 때문에 push 만 한다. MAX값은 계산되지 않는다.

 

 

 

 

 

스택 끝에 담긴 값보다 크기 때문에 push 만 한다. MAX값은 계산되지 않는다.

 

 

이후 모든 블럭을 다 담아줬기 때문에 forEach 문을 나오게 된다.

 

하지만, 아직 stack에는 계산하지 않은 값들이 남아 있기 때문에 이번에는 stack이 빌 때까지 연산을 수행한다.

 

이때 중요한 점은 이 과정에서는 width 를 계산할 때 쓰이는 값이 전체 길이인 N 값이라는 점이다.

 

 

 

남은 스택값들은 아래 과정을 통해 순차적으로 계산된다.

 

 

 

pop 된 값 : [ 3 , 6 ]

 

 

 

pop 된 값 : [ 3 , 5 ]

 

 

pop 된 값 : [ 1 , 1 ]

 

이 경우에는 스택에 남은 값이 없기 때문에 width 길이는 전체 길이 7로 계산한다.

 

width 를 전체로 계산해버리면 만약 중간에 도형이 없어서 끊기는 부분이 있을때 끊지 못하고 전체로 잘못계산되어버리는거아냐? 하고 의문이 들 수도 있다.

 

나도 그렇게 생각했었는데, 애초에 끊기는 부분은 [ 0 , index ] 이렇게 pop 되어 나와질 것이다.

 

그러면 width 곱하기 0 이기때문에 애초에 값이 0으로 되어버려 잘못된 연산을 할 수가 없다.

 

 

또한, 1을 7이 아니고 6이랑 곱해야 맞는거 아닌가 싶을 수 도 있다.

 

하지만, 애초에 [ 1, 1 ] 이 스택에 마지막에 담겨있게된 경우를 생각해보면 이해가 될 것이다.

 

0번 인덱스에 해당하는 높이가 1 보다 높기 때문에 0번 인덱스에 해당하는 값이 pop 된 것이므로 

 

1번 인덱스 이전 높이는 1번 인덱스에 해당하는 높이보다 높은 경우 밖에 없다.

 

따라서, 0번 인덱스에 해당하는 넓이도 넓이를 계산할 때 반드시 포함되는 부분이므로 이때는 전체 길이 7을 곱해주는 것이 올바른 연산이다.

 

 

사실, 이 부분에 대한 해답은

 

각 높이에서 수평선을 쭉 그어 해당하는 넓이를 계산한다.

 

위에서 말한 이 접근법에서 찾을 수 있다.

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [...input_tests] = input.map((v) => v.split(" ").map(Number));

function solution(tests) {
  const calculate = (stack, len, MAX) => {
    const [target, _] = stack.pop();
    let width = 0;
    if (stack.length === 0) width = len;
    else width = len - stack[stack.length - 1][1] - 1;
    MAX = Math.max(MAX, width * target);

    return [stack, MAX];
  };

  tests.forEach((test) => {
    const [N, ...blocks] = test;
    let stack = [];
    let MAX = 0;
    if (blocks.length !== 0) {
      blocks.forEach((block, idx) => {
        while (stack.length !== 0 && stack[stack.length - 1][0] > block) {
          [stack, MAX] = calculate(stack, idx, MAX);
        }
        stack.push([block, idx]);
      });
      while (stack.length !== 0) {
        [stack, MAX] = calculate(stack, N, MAX);
      }
      console.log(MAX);
    }
  });
}

solution(input_tests);