[문제풀이] B1874 스택수열

스택수열

---

  🪅 각 반복문 종료조건을 명확히 알고있느냐, 종료조건을 넣을 알맞은 위치를 찾을 수 있느냐
  🪅 반복문을 돌리고 나서, 스택에 데이터가 남아있다는 것이 의미하는 바를 아느냐
  🪅 인덱스를 만들어야 할 때를 알고 있느냐 => 바깥쪽 for문에 영향을 주지 않기 위해서
  🪅 출력이 많을 때 StringBuilder로 출력할 수 있느냐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * 백준 1874번 스택수열
 * 
 * 입력:
 * 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 
 * 물론 같은 정수가 두 번 나오는 일은 없다.
 * 
 * 출력:
 * 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 
 * 불가능한 경우 NO를 출력한다.
 *
 */
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        Stack<Integer> stack = new Stack<>();

        // 입력값 배열에 저장
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        StringBuilder builder = new StringBuilder();
        builder.append("");

        int num = 1;
        stack.push(num);
        builder.append("+\n");
        // stack이 빌때까지

        int arrIdx = 0;
        // 1부터 N까지 push
        for(int i = 1; i <= N; i++) {
            // top이 만들려는 수열의 현재 숫자와 같으면
            while(!stack.isEmpty() && stack.peek() == arr[arrIdx]) {
                //pop
                int p = stack.pop();
                builder.append("-\n");
                arrIdx++;
            }
            if(arrIdx >= N) {
                break;
            }
            stack.push(++num);
            builder.append("+\n");
        }
        if(!stack.isEmpty()) {
            System.out.println("NO");
            return;
        }
        System.out.println(builder.toString());
    }
}

💡 문제 접근 과정
바깥쪽에 for문을 두고, 안쪽에 while문을 둔 이유는
바깥쪽은 반복횟수가 명확하고, 안쪽은 불명확하기 때문이다.

또한, while 반복문에 조건으로 stack.peek() 앞에 !stack.isEmpty()를 넣은 이유는
stack이 빈상태가 아니어야 stack.peek()를 구할 수 있기 때문이다.
종료문의 위치는 arrIdx++; 해준 후로 잡았다.(그래야 안 헷갈려서)

arrIdx가 필요하다. 처음에는 arr[i-1]로 i값을 최대한 이용하려 했는데,
while문의 반복횟수가 불명확하다 보니까, i++를 얼마나 해주었는지 데이터에 따라 달라져서
바깥쪽 for문의 i를 이용할 것이 아니라 arrIdx값을 따로 주어, 바깥쪽 for문에 영향이 가지 않도록 했다.