백준 1874 스택수열 풀이

이 문제는, 1~n까지의 숫자를 스택의 push, pop 연산을 적당히 사용하여 주어진 수열을 만들 수 있는지 확인하고, 만들 수 있으면, push pop 하는 순서를 추력하는 문제이다. push의 경우, 첫 push 는 1이며, 그 이후 2,3,4... 오름차순으로 push된다.

 

이 문제의 핵심은, 스택에 만들고자하는 수열의 원소가 없으면, push를 연속으로 하고 pop을 해서 무조건 알맞은 숫자를 출력할 수 있고, 스택에 만들고자 하는 수열의 원소가 있으면, 그 원소가 top이여야만 알맞은 수열을 만들 수 있다는 사실이다.

 

package test;


import java.util.*;
public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> input = new ArrayList<Integer>();
        StringBuffer sb = new StringBuffer();
        while(n-->0) {
        	input.add(sc.nextInt());
        }
        int lastinput = 1;
        for(int i=0;i<input.size();i++) {
        	if(Stack.contain(input.get(i))) { // 스택안에 수열의 i번째 원소가 있는 경우 
        		if(Stack.top().intValue()==input.get(i).intValue()) { // top이 수열의 i번째 원소인 경우
        			sb.append("-\n");
        			Stack.pop();
        		}else { // 수열안에 있지만, top이 아닌 경우. 수열만들기 불가.
        			System.out.println("NO");
        			return;
        		}
        	}else { // 스택에 없는 경우.
        		int j = lastinput;
        		for(;j<=input.get(i);j++) {
        			Stack.push(j);
        			sb.append("+\n");
        		}
        		sb.append("-\n");
        		Stack.pop();
        		lastinput=j;
        	}
        }
        System.out.println(sb.toString());
    }
}
class Stack{
	private static ArrayList<Integer> list = new ArrayList<Integer>();
	public static void push(int a) {
		list.add(a);
	}
	public static Integer pop() {
		if(!list.isEmpty()) {
			int a = list.get(list.size()-1);
			list.remove(list.size()-1);
			return a;
		}else {
			return null;
		}
	}
	public static boolean contain(int a) {
		if(list.contains(a)) {
			return true;
		}else return false;
	}
	public static Integer top() {
		if(!list.isEmpty()) {
			int a = list.get(list.size()-1);
			return a;
		}else {
			return null;
		}
	}
}