[20]1874号スタック数列

1874号スタック数列

質問する

スタックは基本的な資料構造の一つであり,コンピュータプログラムを記述する際によく用いられる概念である.スタックは,資料を入れる(push)エントリと抽出する(pop)エントリが同じで,最後に入る資料が最初に現れる(LIFO,Last in Firstout)特性を持つ.
1からnまでの数をスタックに入れ、さらに抽出して並べると、1つの数列を形成することができます.この場合,スタックを進める順序は必ず昇順に従う.任意の数列が与えられた場合、スタックを使用して、その数列を作成できるかどうかを決定できます.もしあれば、pushとpop演算をどの順序で実行すればいいですか.計算プログラムを作成します.

入力

第1行はn(1≦n≦100000)を与える.2行目から、n行目にnより大きい数列の整数である整数が順次与えられる.もちろん、同じ整数は2回も現れません.

しゅつりょく

入力された数列を生成するために、各行に必要な演算を出力します.push演算は+で表し,pop演算は−で表す.不可能であればNOを出力する.

コピー例入力1

8
4
3
6
8
7
5
2
1

コピー例出力1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

コピー例入力2

5
1
2
5
3
4

コピーサンプル出力2

NO

ヒント

1からnまでの整数について、[push,push,push,pop,push,pop,push,pop,push,pop,pop,pop,pop,pop]演算を順次実行することで数列が得られる[4,3,6,8,7,5,2,1].

問題を整理する

この問題の説明はあいまいだ.
検索後に問題を再説明するビデオが見つかりました
1874号スタック問題解説
例を見て問題を理解する.
理解を容易にするために、スタックは처음 [스택의 원소] 끝としてマークされる.
この問題のポイントは、スタックに存在する要素の最大値を覚え、入力した値が最大値より大きい場合、最大値から入力までの数をスタックに蓄積することです.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
4

// 스택 (수열)
[]
[1, 2, 3, 4(pop)]
[1, 2, 3] // 결과

// 스택에 존재했던 최대값
0
4 // 4로 변경

// 연산
[+, +, +, +, -]

// 누적 연산
[+, +, +, +, -]

4を入力します.
現在、数列に4は存在しません.
また、入力値はスタックに存在する最大値よりも大きい.( max < input )
これにより、最大値から入力値までの数字がリフレッシュされます.(1, 2, 3, 4 push)
次に、4をポップアップします.
最終的に4回pushと1回pop演算を行う.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
3

// 스택 (수열)
[1, 2, 3(pop)]
[1, 2] // 결과

// 스택에 존재했던 최대값
4

// 연산
[-]

// 누적 연산
[+, +, +, +, -, -]

3を入力します.
現在、数列に3が存在するのでpop 3.
そこでpop演算を1回行います.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
6

// 스택 (수열)
[1, 2, 5, 6(pop)]
[1, 2, 5]

// 스택에 존재했던 최대값
4
6 // 6으로 수정
 
// 연산
[+, +, -]

// 누적 연산
[+, +, +, +, -, -, +, +, -]

6を入力します.
現在、数列には6は存在しません.
また、入力値はスタックに存在する最大値よりも大きい.( max < input )
これにより、最大値から入力値までの数字がリフレッシュされます.(5, 6 push)
そして6をポップアップします.
最終的に2回pushと1回pop演算を行う.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
8

// 스택 (수열)
[1, 2, 5, 7, 8(pop)]
[1, 2, 5, 7]

// 스택에 존재했던 최대값
6
8 // 8로 수정

// 연산
[+, +, -]

// 누적 연산
[+, +, +, +, -, -, +, +, -, +, +, -]

8を入力します.
スタックには8は存在しません.
また、最大値以上を入力します.
したがって、最大値6以降の整数から入力値まで整数をリフレッシュする.(7,8プッシュ)
次に、8をポップアップします.
最終的に2回pushと1回pop演算を行う.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
7

// 스택 (수열)
[1, 2, 5, 7(pop)]
[1, 2, 5]

// 스택에 존재했던 최대값
8

// 연산
[-]

// 누적 연산
[+, +, +, +, -, -, +, +, -, +, +, -, -]

7を入力します.
現在、数列に7が存在するのでpop 7.
そこでpop演算を1回行います.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
7

// 스택 (수열)
[1, 2, 5(pop)]
[1, 2]

// 스택에 존재했던 최대값
8

// 연산
[-]

// 누적 연산
[+, +, +, +, -, -, +, +, -, +, +, -, -, -]

5を入力します.
現在は数列に5があるのでpop 5です.
そこでpop演算を1回行います.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
2

// 스택 (수열)
[1, 2(pop)]
[1]

// 스택에 존재했던 최대값
8

// 연산
[-]

// 누적 연산
[+, +, +, +, -, -, +, +, -, +, +, -, -, -, -]

2を入力します.
現在の数列には2が存在するためpop 2である.
そこでpop演算を1回行います.

// 입력
[4, 3, 6, 8, 7, 5, 2, 1]

// 현재 입력
1

// 스택 (수열)
[1(pop)]
[]

// 스택에 존재했던 최대값
8

// 연산
[-]

// 누적 연산
[+, +, +, +, -, -, +, +, -, +, +, -, -, -, -, -]

1を入力します.
現在の数列には1が存在するためpop 1である.
そこでpop演算を1回行います.

に答える

単純分割処理で行います.

入力した数値を受け入れます.

(if)入力値がstackdの最後の値と同じである場合pop.

(else)入力値が数列に存在しない場合

(異常処理)최대값 + 1 > numであれば、NOを出力して終了する.

の最大値+1から入力値にプッシュし、最後の入力値をポップアップします.

num>maxの場合、maxはnumに初期化されます.

コード#コード#

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
8
4
3
6
8
7
5
2
1
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//

const t = Number(input());
const inputArr = [];
const stack = [];
let max = 0;
let res = [];

[...Array(t)].forEach(() => {
  inputArr.push(Number(input()));
});

const getRangeArr = (start, end) => {
  return [...Array(end - start + 1)].map((v, i) => i + start);
};

const getPlusArr = n => {
  return [...Array(n)].map(() => '+');
};

for (let num of inputArr) {
  if (stack[stack.length - 1] === num) {
    stack.pop();
    res.push('-');
  } else {
    if (max + 1 > num) {
      res = ['NO'];
      break;
    }
    stack.push(...getRangeArr(max + 1, num));
    stack.pop();
    res.push(...getPlusArr(num - max));
    res.push('-');
    if (num > max) max = num;
  }
}

console.log(res.join('\n'));