백준 1874 - 스택 수열

문제 파악

입력된 수열을 스택이라는 자료구조를 활용해 만드는 문제

스택 : 삽입과 연산이 LIFO(후입선출)로 일어나는 자료구조

풀이

1. 앞으로 몇 개의 수열을 입력받을 건지에 대한 정수 n을 입력받는다.
2. 만들 수열을 하나씩 입력받는다.
   ex) 4 3 6 8 7 5 2 1 -> 이 수열을 만들어 주세요!
3. 1부터 n까지 차례대로 스택에 push push baby 하다가 입력받은 수와 같으면 pop
   a. 같으면 pop을 해서 조건문을 빠져나와 pop한 수 출력
   b. 비교할 수열 값 > 스택 가장 위에 있는 자연수이면 수열을 만 들 수 없다는 것이기 때문에 No 출력!

   코드 작성 중 든 의문 : 원래는 반복문을 돌려가며 push일 때 +, pop일 때 -를 바로바로 하나씩 출력하려고 했는데, 수열이 아예 만들어지지 않으면 No만 출력하고 부호는 출력하면 안된다는 것을 깨달았다. 이러려면 어디다가 +, -를 저장해뒀다가 수열이 만들어지면 한 번에 출력을 해야한다.
   => 그냥 문자열을 + 연산자로 결합하면 계속 자동 형변환이 일어나고 불변성을 가져 실제로 변경되는 것이 아닌 새로운 string 인스턴스가 생성되기 때문에 속도가 왕느려지고 공간도 낭비된다. 따라서 가변성을 가진 스트링버퍼라는 것을 활용해보겠다!!!
   그러려고 했는데 찾아보니 스트링버퍼는 멀티스레드 환경일 때 사용하는게 좋다고 했는데 지금은 메인 스레드 하나만 있으니 스트링빌더라는 것을 활용하는게 낫겠다고 생각했다.

코드

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

public class 스택_수열 {

    public static void main(String[] args) {
        //입력받을 스캐너 개체 생성
        Scanner sc = new Scanner(System.in);

        //수열 개수 입력
        int n = sc.nextInt();
        //입력받을 수열 배열 선언
        int[] suyeol = new int[n];

        //n개의 수열 입력받아 배열에 넣어주기
        for (int i=0; i<n; i++) {
            suyeol[i] = sc.nextInt();
        }

        //정수형 스택 선언
        Stack<Integer> stack = new Stack<>();
        //스트링빌더 선언
        StringBuilder sb = new StringBuilder();
        int start = 1;
        //참이면 반복문 계속 수행행
        boolean run = true;

        //수열 배열 안에 있는 값과 비교하기 위해 for문으로 반복
        for (int i=0; i<suyeol.length; i++) {
            //현재 수열 값과 같아질때까지 push
            if (suyeol[i] >= start) {
                while (suyeol[i] >= start) {
                    stack.push(start);
                    start++;
                    //푸쉬할 때마다 스트링빌더에 + 문자열 넣어주기기
                    sb.append("+\n");
                }
                //같으면 pop
                stack.pop();
                //pop 할 때마다 스트링빌더에 - 문자열 넣어주기기
                sb.append("-\n");
            }
            //스택의 맨 위에 있는 값이 현재 수열의 값보다 크면 안됨!
            else {
                int peek = stack.pop();

                if (peek > suyeol[i]) {
                    System.out.println("NO");
                    run = false;
                    break;
                } 
                else {
                    sb.append("-\n");
                }
            }
        }
        //수열이 만들어졌으면 스트링빌더에 저장된 문자열 출력
        if (run) {
            System.out.println(sb.toString());
        }
    }
}