[백준 1874] 스택수열

문제

 

1874번: 스택 수열

풀이1

수열의 index의 원소와 1부터 시작하는 number를 비교해서

1) 수열의 원소>=number이면 stack에 number를 push하고 number를 1 증가시킨다.

2) 수열의 원소<number이면 stack에서 pop을 하고 index를 1 증가시킨다. 이때 pop한 숫자와 수열의 원소가 같지 않으면 "NO"를 출력한다.

 

이 작업을 index가 N보다 작거나 같을 때까지 반복

 

풀이 2

 2020.10.21

 위의 풀이1에서는 number를 "다음으로 스택에 push 할 숫자" 라고 정의를 했다. 이번에는 number를 "현재까지 스택에 push 한 숫자"라고 정의했다.

 

 

targetArray를 순회하면서 targetArray[index] 와 stack.peek값을 비교한다. targetArray[index]가 크면 number+1에서부터 targetArray[index]까지 push를 하고 마지막에 한번 pop을 한다. 만약 targetArray[index]와 stack.peek값이 같으면 pop을 한다. targetArray[index]<stack.peek()인경우 수열을 만들 수 없다. 

 

 

 

코드(19.12.27 version)

 

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main{
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);

		int N=in.nextInt();
		int[] array=new int[N];
		for(int i=0;i<N;i++) {
			array[i]=in.nextInt();
		}
		
		int num=1;
		int index=0;
		boolean valid=true;
		Stack<Integer> stack=new Stack<Integer>();
		ArrayList<String> plusMinus=new ArrayList<String>();
		
		while(index<N) {
			if(stack.size()==0) {
				stack.push(num++);
				plusMinus.add("+");
			}
			else {
				int arrayNum=array[index];
				if(num<=arrayNum) {
					stack.push(num++);
					plusMinus.add("+");
				}
				else {
					int popNum=stack.pop();
					if(arrayNum!=popNum) {
						valid=false;
						break;
					}
					index++;
					plusMinus.add("-");
				}
			}
		}
		if(valid) {
			for(String s:plusMinus) {
				System.out.println(s);
			}
		}
		else {
			System.out.println("NO");
		}
		
		
	}
}

 

 

코드(20.1.14 version)

 push를 하는 부분 수정 (push를 할때, 하나하나를 검사해서 push 하는게 아니라 수열의 숫자까지 push를 하게끔) 

package stack;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class StackNumber {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		int[] numArray = new int[N];
		for (int i = 0; i < numArray.length; i++) {
			numArray[i] = in.nextInt();
		}

		Stack<Integer> stack = new Stack<Integer>();
		ArrayList<String> plusMinus = new ArrayList<String>();

		int pointer = 0;
		int pushNum = 1;
		boolean valid = true;

		while (pointer < N) {
			int num = numArray[pointer];
			if (stack.isEmpty()) {
				while (pushNum <= num) {
					stack.push(pushNum++);
					plusMinus.add("+");
				}
			} else {
				int topNumber = stack.peek();
				if (num != topNumber) {
					if (num < stack.peek()) {
						valid = false;
						break;
					} else {
						while (pushNum <= num) {
							stack.push(pushNum++);
							plusMinus.add("+");
						}
					}
				} else {
					System.out.println("pop");
					stack.pop();
					pointer++;
					plusMinus.add("-");
				}

			}
		}
		// 출력
		if (valid) {
			for (String opertaion : plusMinus) {
				System.out.println(opertaion);
			}
		} else {
			
			System.out.println("NO");
		}
	}
}

 

2020.10.21

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {
    public static int N;
    public static Stack<Integer> stack;                 
    public static ArrayList<Integer> targetArray;       //스택에서 push pop 하면서 만들고사 하는 수열(목표수열)
    public static Queue<String> operation;              //목표 수열을 만들기 위한 연산(+,-)

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());

        //초기화
        targetArray = new ArrayList<>();
        for(int index = 0 ; index<N; index++){
            targetArray.add(Integer.parseInt(br.readLine().trim()));
        }
        stack = new Stack<>();
        operation = new LinkedList<>();

        if(check()){
            while(!operation.isEmpty()){
                bw.write(operation.remove()+"\n");
            }
        }
        else{
            bw.write("NO");
        }
        bw.flush();


    }
    // targetArray를 순회하면서 targetArray[index]와 stack.peek()값을 비교한다
    public static boolean check(){
        boolean valid = true;

        int num = 0;  // 현재까지 스택에 push한 마지막 수
        for(int index = 0; index<targetArray.size(); index++){
            int arrayNum = targetArray.get(index);

            if(stack.isEmpty()){
                while(num<arrayNum){
                    stack.push(++num);
                    operation.add("+");
                }
                stack.pop();
                operation.add("-");
            }
            else{
                if(stack.peek()==arrayNum){
                    stack.pop();
                    operation.add("-");
                }
                else if(stack.peek()<arrayNum){
                    while(num<arrayNum){
                        stack.push(++num);
                        operation.add("+");
                    }
                    stack.pop();
                    operation.add("-");
                }
                else{
                    valid = false;
                    break;
                }
            }
        }

        return  valid;
    }
}