(BOJ / Node.js) 17298. 오쿤수

by

#17298: 오쿤수

첫 번째 라인은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다. 두 번째 행에는 시퀀스 A의 요소 A1, A2, …, AN(1 ≤ Ai ≤ 1,000,000)이 포함됩니다.

www.acmicpc.net

'추천 관련글,

크기 N의 시퀀스 A = A1, A2, …, AN이 있습니다. 시퀀스의 각 요소 Ai에 대한 Oaken 번호 NGE(i)를 찾고 싶습니다. Ai가 가장 큰 수는 오른쪽의 수 중에서 가장 왼쪽에 있는 수이고 Ai보다 큽니다. 해당 숫자가 없으면 OKN 숫자는 -1입니다.

예를 들어 A = (3, 5, 2, 7), NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1인 경우. A = (9, 5, 4, 8), NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1 이면.

기입

첫 번째 라인은 시퀀스 A의 크기 N(1 ≤ N ≤ 1,000,000)을 제공합니다. 두 번째 행에는 시퀀스 A의 요소 A1, A2, …, AN(1 ≤ Ai ≤ 1,000,000)이 포함됩니다.

누르다

총 N개의 숫자 NGE(1), NGE(2), …, NGE(N)을 공백으로 구분하여 출력한다.

예시 입력 1 복사

4
3 5 2 7

샘플 출력 1 복사

5 7 7 -1

해결하다

  • 다음 의사 코드를 작성하고 해결했습니다.
  1. 전체 배열을 반복하는 루프(최대 n-1)
  2. 옥탄가를 바로 찾을 수 있는지 확인하십시오(바로 거기에 있다면)
  3. 발견되면 NGE 어레이 인덱스에 큰 숫자를 저장합니다.
  4. 스택이 비어 있지 않으면 스택의 상위 값이 큰 숫자인지 확인하고 그렇지 않을 때까지 계속합니다.
  5. 찾지 못하면 스택에 푸시(값, 인덱스 형식)
  • NGE 배열을 만든 후 -1로 초기화했습니다. (큰 숫자가 없을 경우 기본값은 -1로 출력하므로 초기화를 했다면 따로 처리할 필요는 없습니다.)

암호

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

const n = +input(0);
const arr = input(1).split(' ').map(el=>+el);

const NGE = Array(n).fill(-1);
const stack = ();

for(let i = 0; i < n-1; i++) {
    if(arr(i) < arr(i+1)) {
        NGE(i) = arr(i+1)

        while(stack.length) {
        const (value, index) = stack(stack.length-1);
        if(arr(i+1) > value) {
            NGE(index) = arr(i+1);
            stack.pop();
        } else break;
    }
    
    }
    else stack.push((arr(i), i));
}


console.log(NGE.join(' '));