[Java/백준/스택] 1874 - 스택 수열

문제

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

코드

처음 문제를 이해하는 것부터 난관이었다.

알고보니 1~N 순서대로 스택에 push하는 것이었다.

숫자를 순서대로 Stack에 push하면서 입력받은 수열 seq[idx]와 같을 때 pop을 시켜주었다.

아닌 경우는 push하도록 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main{
	public static void main(String[] args) throws IOException{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
          // seq : 수열 배열, inputArr : 1~N의 숫자가 들어갈 배열
          int[] seq = new int[N];
          int[] inputArr = new int[N];

          ArrayList<String> answer = new ArrayList<>();
          for(int i=0; i<N;i++){
              seq[i] = Integer.parseInt(br.readLine());
              inputArr[i] = i+1;
          }

          Stack<Integer> stack = new Stack<Integer>();

          //idx : seq의 인덱스, inputIdx : inputArr의 인덱스
          //flag : seq 검사가 완료되었을 때 true로 전환
          //full : inputArr의 모든 원소가 push 되었을 때 증가
          int idx = 0;
          int inputIdx = 0;
          boolean flag = false;
          int full = 0;

          while(idx<seq.length){
              //stack이 비어있지 않다. && 검사할 seq의 원소 == stack의 top --> pop!
              if(!stack.isEmpty() && seq[idx]==stack.peek()){
                  if(idx==seq.length-1){
                      flag=true;
                  }
                  stack.pop();
                  idx++;
                  answer.add("-");
              }else{
                  //inputArr에 push할 숫자가 남아 있을 때
                  if(inputIdx!=N){
                      stack.push(inputArr[inputIdx]);
                      inputIdx++;
                  }
                  //inputArr에 push할 숫자가 남아있지 않을 때 (top!=seq[idx])
                  else if(inputIdx==N){
                      break;
                  }
                  answer.add("+");
              }
          }

          if(flag){
              for(String ans : answer){
                  System.out.println(ans);
              }
          }else{
              System.out.println("NO");
          }
	}		
}