백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 1725 히스토그램 [ 스택 ]

백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 1725 히스토그램 [ 스택 ]

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

1725번: 히스토그램

 

 

 

문제풀이 소감 🧑‍💻

 

6549때 고생해서 푼 덕분에 덤으로 풀어진 문제이다.

 

문제 요구사항 풀이법 자체는 6549문제와 똑같으니 6549를 풀어봤다면 어렵지 않게 풀 수 있을 것이다.

 

굳이 푸는 순서를 말하자면 1725 를 먼저 풀고 6549를 푸는게 더 맞는 것 같다. (크게 상관 X)

 

 

 

반례

 

7
2
1
4
5
1
3
3

 

Answer : 8

 

 

3
2
1
2

 

Answer : 3

 

9
3
2
1
0
1
2
3
3
3

 

Answer : 9

 

 

 

 

해결 전략 📝

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Platinum-5-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-Nodejs-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-6549-%ED%9E%88%EC%8A%A4%ED%86%A0%EA%B7%B8%EB%9E%A8%EC%97%90%EC%84%9C-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95-%EC%8A%A4%ED%83%9D

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

 

* 풀이법에 대해서는 6549 문제 풀이에 상세히 적어두었습니다. 참고바랍니다.

 

 

 

 

 

정답 💯

 

 

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

const [input_N, ...input_blocks] = input.map(
  (v) => v.trim().split("\n").map(Number)[0]
);

function solution(N, blocks) {
  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];
  };

  let stack = [];
  let MAX = 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);
  }

  return MAX;
}

console.log(solution(input_N, input_blocks));