[JavaScript] 백준 17298 오큰수 (JS)

오큰수

📚 문제 설명

크기가 N 인 수열이 있다고 했을 때, 각각의 원소의 오큰수라는 것을 구하려고 한다.
만약 오큰수가 없다면 -1을 줌

오큰수 : 오른쪽에 있는 것들 중 자신보다 큰 숫자를 의미

예시

 [3, 5, 2, 7]인 경우
 3 - 3의 오른쪽에서 3보다 큰 숫자는 5
 5 - 5의 오른쪽에서 5보다 큰 숫자는 7
 2 - 2의 오른쪽에서 2보다 큰 숫자는 7
 7 - 7의 오른쪽에서 7보다 큰 숫자는 없다 따라서 -1
 
 결과 - 5, 7, 7, -1

👨🏻‍💻 풀이 과정

해당 문제는 스택에 있는 값에서 자신의 좌 / 우에 있는 자신보다 큰 값을 찾는 문제이기 때문에 Monotonic Stack(단조스택)을 이용해서 풀면 된다고 생각할 수 있다. (Monotonic Stack 에 대한 설명은 여기서 확인)
그런데 이 문제에서 조금 다르게 생각할 점은 배열의 끝에서부터 값을 stack 에 추가하며, 내림차순을 만들어 줘야하는 것이 아주 약간 다른 점이다. 그럼 순서대로 로직에 대해 생각해보자.

• 반복문을 통해 배열 끝에서부터 확인
  • 만약 stack 에 값이 있다면, input[i] 값과 비교
    • 만약 스택의 마지막 값이 input[i] 보다 작다면 pop()
    • 아니라면 break
  • 스택에 input[i] 를 넣어줌
  • 만약 스택의 길이가 1이면 answer 에 -1 을 넣어줌 아니라면, 스택의 마지막에서 2번째 값을 넣어줌

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());
    input = input.shift().split(' ').map(Number);

    let stack = [];
    let answer = [];
	// 배열의 마지막부터 확인 
    for (let i = N - 1; i >= 0 ; i--) {
        while (stack.length) {
          // 스택에 있는 값을 비교하며 스택을 내림차순으로 정렬
            if (stack[stack.length - 1] <= input[i]) {
                stack.pop();
            }else break;
        }
        stack.push(input[i])
      	// 스택에 값이 1개만 들어있으면 자기 자신뿐이니까 -1을 리턴
        if (stack.length === 1) {
            answer.push(-1);
        } else {
          //만약 스택의 길이가 2 이상이면 마지막에서 2번째 값이 자신 오른쪽의 가장 큰 건물
            answer.push(stack[stack.length - 2]);
        }
    }
	// for문에서 뒤에서부터 계산해서 push 해줬기 때문에 순서가 거꾸로임 따라서 reverse() 필요
    console.log(answer.reverse().join(' '));

🧐 후기

Monotonic Stack(단조 스택) 알고리즘을 이용하는 문제였다. 처음에는 Monotonic Stack(단조 스택)이 정말 이해하기 어려웠고 힘들었지만, 이제 이와 비슷한 문제들을 보면 바로 생각이 나는 것 같다.