[BOJ 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

問題を解く心得

これは,問題出力がいつNOであるかを決定するのに長い時間がかかる問題である.(問題を正しく読みましょう、(LIFO, Last in First out) 특성と書いてあるのでいっそスタックを書きます…)
例に従って、1、2、3、4を追加し、pop 4、3を追加し、6に遭遇すると5、6を追加するので、昇順pushスタックのidxの変数を知る必要があります.
qリストとnumスタックが完成して、すぐにプリントアウトしようと思ったのですが、不可能ならNOをプリントするので、答えをプリントするために結果リストを作成して入れました.
同様に,for~else文でbreak文に遭遇した場合,NOを出力しなければ正解出力を生成する.
sepのデフォルト値は「」であり,適切に操作することで正解出力のfor文を減らすことができる.

マイコード

N = int(input())

q = []
num = 0
result = []
for _ in range(N):
    k = int(input())

    if num < k:
        while num < k:
            num += 1
            q.append(num)
            result.append('+')

        result.append('-')
        q.pop()
    else:
        if q[-1] != k:
            print('NO')
            break
        else:

            result.append('-')
            q.pop()
else:
    print(*result, sep='\n')