알고리즘: 백준-1874

문제 링크

설명

스택 자료구조를 사용해 주어진 입력과 출력을 시뮬레이션 하는 문제이다.

1. n을 입력받아 오름차순으로 n이하의 자연수가 스택에 차례대로 들어간다
2. 스택으로부터의 출력 순서가 주어지며(자연수), 수를 적절하게 넣고 빼며 출력순서를 따라갔을 떄 push, pop할때마다 + 혹은 - 를 출력한다.
3. 주어진 출력 순서를 스택으로 구현이 불가능 하면 NO를 출력한다.

풀이

1. 첫째줄에 주어진 수(n) 만큼 반복한다
2. 입력받은 값(k)까지 스택에 push, pop하며 해당값을 스택으로부터 출력한다.

• currentNumber 변수를 이용해 현재까지 입력된 수의 크기를 전역으로 관리

3. 만약 k가 currentNumber보다 작다면, 즉시 pop(t)한다.
4. 만약 t가 k와 다르다면, NO을 출력하고 종료한다.
5. 매번 push, pop 할 때마다, queue(result)에 +혹은 -를 출력한다.
6. result를 출력하고 종료한다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    Stack<Integer> stack = new Stack<>();
    Queue<Character> result = new LinkedList<Character>();

    public void solve(){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int current = 0;

        for(int i = 0; i < n; i++){
            int next = scanner.nextInt();
            while(current < next){
                stack.push(++current);
                result.add('+');
            }

            Integer pop = stack.pop();
            result.add('-');

            if(pop != next) {
                System.out.println("NO");
                return;
            }
        }

        for(Character c : result)
            System.out.println(c);
    }

    public static void main(String[] args) {

        Main main = new Main();
        main.solve();

    }


}