[アルゴリズム解答][Python]白駿17298号:大数

13661 ワード
アルゴリズム#アルゴリズム# 白駿17298 パイ 五大数 白駿 テキストリンク

白駿17298題リンク:https://www.acmicpc.net/problem/17298


📑 問題の説明


数列のサイズと数列が与えられたときに、各数列の各位置に整数を求めるプログラムを作成します.
五大数とは、各位置の数字のうち、右にある数字のうち、各位置の数字より大きく、最も左にある数字を指す.
例えば、数列が3 5 2 7の場合
3の5大数は5 2 7の中で3より大きく,最も左側に位置する5となる.
5の5大数は7、2の5大数は7、7は5大数にならないので-1を出力します.
入力:数列のサイズ、数列
出力:大数

💡 トラブルシューティング方法


この問題は結局解けず、答えを見て解決した.
(今まで私のコードの中でどの部分が間違っているのかまだ見つかっていません...)
Tip! stackを使用してindexを保存!
  • の現在の数字がスタックでプッシュされたインデックスの数字より小さい場合、現在の数字に対応するインデックスはスタックにプッシュされます.
  • の現在の数字がスタックに格納されているインデックスの数より大きい場合、インデックスを検索するエラーの数になるため、スタックはインデックスをポップアップします.次に、現在の数値に対応するインデックスを押します.
    • 例:9 5 4 8
    初期スタック[0]
    初期数列インデックス=1
    1.index=1の場合、
    数列[stack[1]=9(前の数字)>数列[index]=5(現在の数字)のためindex=1をstackにプッシュ
    --> stack[1 0]

  • index=2の場合、
    数列[stack[1]=5(前の数字)>数列[index]=4(現在の数字)のためindex=2をstackにプッシュ
    --> stack[2 1 0]

  • index=3の場合、
    数列[Stack[1]=4(前の数字)<数列[index]=8(現在の数字);stack.pop(=2)は、現在の数値が前の数値より大きい場合にプロセスを繰り返し、繰り返し完了後に現在のインデックスをスタックにプッシュします.
    -->スタック[10]-->数列[958]
    -->スタック[0]-->数列[9888]
    --> stack[3 0]

  • stackにindex値が残っている場合は、大きな数はできないことを示すため、その数列の桁数は-1に変更されます.
    -->数列[1.8-1]

    • 💻 コード#コード#


    グマンスコード
    import sys

def check_neg(n,num_list, order):

    index_stack = list()
    index_stack.append(0)
    result = list()
    for i in range(1, n):
        if(num_list[i] < num_list[index_stack[-1]]):
            index_stack.append(i)
        else:
            num_list[index_stack.pop()] = num_list[i]
            if(len(index_stack)>0):
                while(len(index_stack)):
                    if (num_list[index_stack[-1]]<num_list[i]):
                        num_list[index_stack.pop()] = num_list[i]
                    else:
                        break
            index_stack.append(i)


    if(len(index_stack) > 0):
        for i in range(len(index_stack)):
            num_list[index_stack.pop()] = -1
    print(num_list)
if __name__ == '__main__':
    n = int(sys.stdin.readline())
    num_list = [ int(x) for x in (sys.stdin.readline().split())]
    order = sorted(num_list)
    check_neg(n, num_list, order)
    正しいコード
    import sys

def check_neg(n,num_list):

    index_stack = list()
    index_stack.append(0)

    for i in range(1, n):
        while index_stack and num_list[index_stack[-1]] < num_list[i]:
            num_list[index_stack.pop()] = num_list[i]
        index_stack.append(i)

    if(len(index_stack) > 0):
        for i in range(len(index_stack)):
            num_list[index_stack.pop()] = -1
    return(num_list)

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    num_list = [ int(x) for x in (sys.stdin.readline().split())]

    result = check_neg(n, num_list)
    for i in result:
        print(i, end=" ")

    💟 詳細

  • while listは、listに要素がある場合は非True、False
    • を意味します.
    [C言語]白駿2108:統計学
    hash map