[伯俊]14298-呉大洙(Java)

11662 ワード
白駿 アルゴリズム#アルゴリズム# スタック テキストリンク


まずはこれが私が初めて出した黄金問題…!完全に自分の力で解決することはできないが、失敗した.
各段階の解答では,スタックカテゴリの問題であるため,より多くのヒントを与えた.

方法


この問題を初めて読んだとき、なぜスタックを書くのですか.という考えが生まれた.最初に思いついた方法は二重砲口です.しかし、砲撃すると時間的複雑度はO(n^2)で、タイムアウトで通過できない.だから自然とスタックを使う理由がわかりました.

論理的説明


まず、ここでは、数列の各要素を指す변수 tが必要であり、答えを求めるためには、一時的に置かれるtemp스택と、真の答えを含むNGE스택が必要である.
t(数列)は後ろから順番にチェックします.
  • tempが空(=t以下を示す)NGE.push(-1);temp.push(t);
  • tempが空でない場合、tempはt未満の値をすべてポップアップし、削除します.=>>tempはtの右側にあり、大きな値しかありません.
  • tempのすべての要素を削除すると、isEmpty()=trueになります.NGE.push(-1); temp.push(t);
  • でなければ、NGE.push(temp.peek());=>tの最大数temp.push(t);

    • インプリメンテーションコード

    import java.io.*;
import java.util.*;
import java.util.Stack;

public class No17298_오큰수 {
    public static void main(String[] args) throws IOException, EmptyStackException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        
        String[] str = br.readLine().split(" ");
        
        Stack<Integer> temp = new Stack<>();
        Stack<Integer> NGE = new Stack<>();

        int t=0;

        for (int i=tc-1;i>=0;i--) {
            t=Integer.parseInt(str[i]);

            if(temp.isEmpty()) {
                NGE.add(-1);
                temp.push(t);
            }
            
            else {
                while (!temp.isEmpty() && t >= temp.peek())
                    temp.pop();

                if (!temp.isEmpty()) {
                    NGE.add(temp.peek());
                }
                else {
                    NGE.add(-1);
                }
                temp.add(t);
            }

        }

        
        for (int i=0;i<tc;i++)
             sb.append(NGE.pop()+" ");

        System.out.println(sb.toString());
        
    }
}
    これにより時間複雑度をO(N)に低減することができる.
    最初は3つのスタックを使っていたが、またタイムアウトした.この方法はまだ難しいと思いますが、解題方法さえ身につけていれば、ゆっくり練習すればいいと思います!
    第1週
    ステートマシンの簡単な実装_1