💜 백준 1874번 스택 수열

1. 문제 설명

1874 스택수열 문제 설명

1. 1~N까지 오름차순으로 스택에 하나씩 집어넣는다.
2. 스택에 하나씩 들어올 때, 적절히 POP하여, 문제에서 원하는 수열을 만들 수 있는지 구하라
3. 만들 수 있다면 PUSH = + , POP = - 로 그간 해왔던 명령어를 출력하고,
   만들 수 없다면 NO를 출력하라

2. 문제 푸는 방법

A. 첫 번째 방법 (STACK 자료 구조 이용)

(1) 답이 되는 수열(이하 ans)과 스택에 입력하는 순서인 오름차순 수열(이하 arr)을 배열에 저장했다.

(2) 둘 다 지시자를 가지고 있다.
ans의 지시자를 ansIndicator, arr의 지시자를 arrIndicator라고 할 때,

​ a. arrIndicator가 가르키고 있는 것이 ansIndicator보다 작거나 같으면 stack에 arrIndicator가 가르키고 있는 것을 Push하고 arrIndicator를 하나 올린다.
b. Stack의 맨 꼭대기 값과 ansIndicator가 가르키고 있는 값이 같으면, Stack 꼭대기 값을 pop하고 ansIndicator를 하나 올린다.
c. 만약 Stack 꼭대기의 값이 ansIndicator보다 크면, Stack에서 아무리 POP해도 원하는 수열을 만들 수 없기 때문에, NO를 출력 한다.

B. 두 번쨰 방법 (배열을 스택처럼 이용)

[변수에 대한 설명]

a. top = Stack의 Peek를 가르키는 것을 배열에서 구현하기 위해 사용하는 변수로, 배열에서 제일 최근에 들어온 값을 지칭하는 변수이다.

b. index = 답이 될 수열의 특정 원소를 가르키고 있는 지시자이다.

[문제 푸는 방법]

(1) for문을 1 ~ N 까지 돈다.
(2) stack에 일단 하나 집어 넣는다.
(3) 다음 while 문 돌면서 stack의 top과 index가 가르키고 있는 ans의 원소가 같은지 확인한다.
(4) 만약 같다면, top-- (pop하고 그 밑에걸 가르키는 것을 의미), index++ (다음 원소를 가르키는 것을 의미) 한다.
(5) 1~n까지 다 돌고 나면, stack에 잔재해 있는 나머지 값들에 대해서 (4)를 한번 더한다.
(6) 근데 만약에 (5)를 했는데도 Stack에 잔재해 있는 값이 남아있다면, 답이 되는 수열을 못 만든다는 소리가 되므로, NO를 출력한다.

3. 코드 분석

A. 첫 번쨰 방법에 대한 풀이

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

/*
* 1874번 스택 수열 
* */


public class Main {

    static int N;

    static int [] ans;

    static int [] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 1. 입력 받기---------------------------------------------------------------

        N = Integer.parseInt(br.readLine());

        arr = new int [N];
        ans = new int [N];

        for (int i = 1; i <= N; i++) {
            arr[i-1] = i;
            ans[i-1] = Integer.parseInt(br.readLine());
        }


        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();

        // 2. 배열과 답의 값을 비교해서, 배열 <= 답이면, 배열의 표시자를 하나씩 올리면서, [stack]에 집어넣는다.
        // 3. stack.peek() == 답이면, stack 에서 pop 하고, 답의 표시자를 하나 올린다.
        // 4. stack.peek() > 답이면 NO를 출력하고 프로그램을 종료한다.

        int ansIndicator = 0;
        int arrIndicator = 0;

        while (ansIndicator < N) {

            while (arrIndicator < N && arr[arrIndicator] <= ans[ansIndicator]){
                sb.append("+\n");
                stack.push(arr[arrIndicator]);
                arrIndicator++;
            }

            while (!stack.isEmpty() && stack.peek() == ans[ansIndicator]){
                stack.pop();
                sb.append("-\n");
                ansIndicator++;
            }


            if(!stack.isEmpty() && stack.peek() > ans[ansIndicator]){
                System.out.println("NO");
                return;
            }


        }


        System.out.println(sb);


    }
}

B. 두 번쨰 방법에 대한 풀이

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

/*
* 1874번 스택 수열
* */


public class Main {

    static int [] ans;

    public static void main(String[] args) throws IOException {

        // 1. 값 입력 ---------------------------------------------------------
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        ans = new int [N];

        for (int i = 0; i < N; i++) {
            ans[i] = Integer.parseInt(br.readLine());
        }

        // [stack]을 배열로 구현
        int [] stack = new int [N];

        // top은 Stack의 지시자,  stack 배열에 값이 찰수록 올림. -> 뺄 때마다 내림
        int top = -1;
        StringBuilder sb = new StringBuilder();
        int index = 0;

        // stack 에 값 넣으면서 바로바로
        for (int i = 1; i <= N; i++) {

            // 1) 같은 경우가 아니라면 stack에 오름차순으로 값을 push 한다.
            stack[++top] = i;
            sb.append("+\n");

            // 2)  stack에 값이 존재하고, stack의 탑이랑 뽑아야할 값이랑 같으면 POP한다.
            while (top != -1 && stack[top] == ans[index]){

                top--;                      // 지시자 한 단계 내리기 pop을 구현한 것
                index++;                    // 지금 답은 이제 해결 했음으로 다음으로 넘어간다.
                sb.append("-\n");           // 값 넣기
            }
        }

        // 3) Stack이 empty가 아니고, stack의 peek이 답의 값과 같으면 pop
        while (top != -1 && stack[top] == ans[index]){
            top --;
            index ++;
            sb.append("-\n");
        }

        // 4) 3번에서 [stack]의 peek 과 현재 출력해야 하는 답 부분이 어긋나면 해당 문제는 풀 수 없는 문제 이므로
        //    stack 배열을 맨 아래까지 보지 않은 채, while loop를 나간다.
        //    따라서 top이 맨 밑바닥인 -1까지 오지 않으면 NO를 출력한다.
        System.out.println(top == -1? sb : "NO");
    }
}