[백준 1874 with Java] 스택수열

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

1874번: 스택 수열

 

스택 수열이라는 문제 이름에 맞게

 

스택을 활용해서 풀어주면 쉽게 풀린다.

 

1~n 까지 스택에 push하다가

 

입력받은 배열 값과 비교하면서 pop해주는 식으로 풀어보았다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        Stack st = new Stack();
        ArrayList<String> ans = new ArrayList();
		int n = Integer.parseInt(br.readLine());
		
		// 입력 담을 array
		// 0을 사용하지 않기 때문에 +1을 해줌
		int[] a = new int[n + 1]; 
		// 입력 array a에서 pop할 인덱스 값
		int m = 1;
		
		// 입력 세팅
		for (int i = 1; i <= n; i++) {
			a[i] = Integer.parseInt(br.readLine());
		}
        
        //스택에 1부터 쌓으면서, a 배열의 1번째 인덱스와 같으면 pop
		for (int i = 1; i <= n; i++) {
			st.push(i);
			ans.add("+");
			while (!st.empty() && st.peek().equals(a[m])) {
				st.pop();
				ans.add("-");
				m++;
			}
		}

		if (st.empty()) {
			for (String s : ans) {
				System.out.println(s);
			}
		} else {
			System.out.println("NO");
		}
		
		br.close();
	}	
}