[BOJ] 백준 1874 스택 수열

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

 Input 

8

4 3 6 8 7 5 2 1

 

 Output 

+

+

+

+

-

-

+

+

-

+

+

-

-

-

-

-

arr = [1 2 3 4 5 6 7 8]

Stack = [] 이 주어졌을 때, push/pop 연산을 이용하여 

입력 받은 수열 순서로 재배치 가능 여부를 출력하는 문제이다.

1~8까지에 놓여진 수를 차례로

push, push, push, push, pop

pop, push, push, pop, push

push pop, pop, pop, pop, pop

연산하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

 

① 임의로 주어진 수열을 만족하기 위해서는 일치하지 않은 숫자는 push

     Target 숫자 순서가 되기까지 Stack에 쌓아준다.

② Target 숫자가 나타나면 Stack에 push/pop 단계를 수행.

    pop은 Target 숫자이면서 Stack에 제일 마지막에 push된 원소이다.

③ pop을 해야 하는데, Target 숫자가 아니라면 『no』 출력

arr = [3, 4, 5] / Target = [5, 3, 4] / Stack = [] 존재

 

Target = 5

arr = [ ]  / Stack = [3, 4 , 5] 인 상태에서 pop

 

Target = 3

arr = [] / Stack = [3, 4]에서 pop을 해봤자 3을 처리하지 못함.

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        int N = Integer.parseInt(sc.next());
 
        Queue<Integer> arr = new LinkedList<>();
        // 수열 입력
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(sc.next()));
        }
 
        // 알고리즘을 구현하는 데 사용한 stack
        Stack<Integer> stack = new Stack<>();
        // 정답을 저장한 queue
        Queue<String> answer = new LinkedList<>();
 
        int idx = 1;
        // 주어진 모든 수에 대해서 해결될 때까지
        while (!arr.isEmpty()) {
            // 수열에서 원소 1개를 지정
            int target = arr.poll();
 
            // 아직 stack에 넣은적이 없기에 해당 단계가 나올 때까지 push한다.
            if (target > idx) {
                // 같아질때까지 스택에 push한다.
                while (target != idx) {
                    stack.push(idx);
                    answer.add("+");
                    idx++;
                }
            }
            // 때마치 등장하는 숫자이면
            if (target == idx) {
                // 넣었다가 뺀다.
                answer.add("+");
                answer.add("-");
                // 다음 단계를 진행
                idx++;
                continue;
            }
 
            // 기존에 나왔던 숫자이므로 스택에 들어 있을 것이다.
            // 스택에서 값을 꺼내 확인해야 한다.
            // 스택안에 top 위치에 있어야 수열을 형성할 수 있다.
            if (target < idx) {
                int popValue = stack.pop();
                if (popValue == target) { // 꺼낸 수간 일치한다면 문제 없지만.
                    answer.add("-");
                } else { // 일치하지 않은 경우 별도의 스택이 존재하지 않기에 만들수 없는 수열에 해당된다.
                    System.out.println("NO");
                    return;
                }
            }
        }
 
        while (!answer.isEmpty()) {
            System.out.println(answer.poll());
        }
 
    }
}