[Java] BOJ 1874 스택 수열

문제 

문제 링크 https://www.acmicpc.net/problem/1874

• 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
• 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
• 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.
• 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
• 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

아이디어

• 만들어야 되는 수열을 먼저 받아놓고 배열에 저장한 후, 1부터 n까지 stack에 하나씩 넣으면서 연산결과 배열에 ' + '를 넣어주고 stack의 꼭대기 값과 만들어야되는 수열의 해당 번째의 숫자가 같다면 연산결과 배열에 ' - '를 넣어주고 stack 제일 위 숫자를 빼서 결과 배열에 넣는다.
• while문을 통해서 꼭대기가 같으면 계속해서 빼주고 만약 같지 않거나 stack이 비었을 경우 while문을 종료하고 다음 for문으로 돌아가서 다음 숫자를 stack에 넣는다. 
• 위의 과정을 반복하며 n까지 모두 입력했을 경우, 반복문을 끝내고 만약 stack에 남은 숫자들이 있다면 따로 for문을 통해서 결과배열에 순서대로 넣어준다.
• 그렇게 만든 결과배열과 만들어야되는 수열 배열을 비교했을 때, 두 배열이 같다면 연산결과를(' + ' 와 ' - '를 넣은 배열) 출력하고 같지 않다면 'NO'를 출력한다.    
  
  

겪은 시행착오

• X

오늘 앞에서 풀었던 두문제보단 나름 수월히 풀었던 것 같다..!

코드

import java.io.*;
import java.util.*;

public class BOJ1874 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        // 만들어야될 수열
        int cal[] = new int[n];

        // 결과 배열
        int result[] = new int[n];

        // stack을 계산할 stack
        Stack<Integer> s = new Stack<>();

        List<String> out = new ArrayList<>();

        // 순서대로 숫자를 넣어줌
        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(br.readLine());

            cal[i] = num;
        }

        // 만들어야될 수열의 순번
        int cnt = 0;

        // 1부터 n까지 반복
        for(int i = 1; i <= n; i++){
            // i를 stack에 넣음
            s.push(i);

            // stack에 넣었으므로 배열에 + 추가
            out.add("+");

            while(true){
                // 만약 만들어야되는 수열의 해당 순번 숫자와
                // stack에 꼭대기 숫자가 같다면
                // stack에서 꼭대기 값을 제거 후
                // 결과값 저장 배열에 - 추가
                // 그리고 결과 배열에 해당 숫자 추가
                if(cal[cnt] == s.peek()){
                    out.add("-");
                    result[cnt] = s.peek();
                    s.pop();
                    // 다음 순번으로 넘어감
                    cnt = cnt + 1;
                }
                // 만약 두개의 숫자가 같지 않다면 while문 종료
                else{
                    break;
                }

                // 만약 결과배열에 끝까지 다 들어갔거나 stack이 비었다면
                // while문 종료
                if(cnt == (n - 1) || s.isEmpty()){
                    break;
                }
            }
        }

        // n까지 모두 입력을 했으므로 stack에 남은
        // 숫자는 모두 빼는 방법밖에 없음
        for(int i = 0; i < s.size(); i++){
            out.add("-");
            result[cnt] = s.peek();
            s.pop();
            // 다음 순번으로 넘어감
            cnt = cnt + 1;
        }

        // 두 수열이 같은지 판별할 변수
        boolean same = true;

        // 만들어야되는 수열과 만든 수열이 같은지 비교
        for(int i = 0; i < n; i++){
            if(cal[i] != result[i]){
                same = false;
                break;
            }
        }

        // 만약 두 수열이 같다면 연산결과를 저장한 배열을 출력
        if(same){
            for(int i = 0; i < out.size(); i++){
                sb.append(out.get(i) + "\n");
            }

            System.out.println(sb);
        }
        // 같지 않다면 NO 출력
        else{
            System.out.println("NO");
        }
    }
}