[백준 2024/01/18] 1874번 스택 수열

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

1874번: 스택 수열

 

1. 접근 방법

첫 번째, 예시를 예로 들어보자.

백준 첫 번째 출력 예시

 

 

우선 구하고자 하는 순서를 배열로 만든다.
예제 입력 1을 예시로 하여 보자.)배열 A = [ 4, 3, 6, 8, 7, 5, 2, 1] 로 구성될 것이다.
다음으로, stack을 [1, 2, 3, 4, 5, 6, 7, 8] 로 구성하여, 1이 제일 위에 오도록 한다.
즉,
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| 7 |

| 8 |

----
로 구성이 될 것이다.stack에서 배열을 차례로 넘어가며, 원하는 수를 찾으려 한다.
즉, 4를 찾을 때까지 1, 2, 3, 4 를 새로운 stack인 final_stack에 넣는다.

만약 4를 찾게 되면, 이때부터, final_stack에서 pop을 시작한다.
먼저 4를 pop한 후, 다음 A 배열의 값인 3이 final_stack에서 pop이 가능한지 여부를 확인한다.확인하여보니, pop이 가능하기에 pop을 해주고, 다음 배열 A의 값을 비교해준다.
다음으로 6이지만, 현재 final_stack에 남아있는 값은 2이므로, pop이 안되기에 while문을 중단하고, 다시 6을 찾을 때까지 숫자들을 final_stack에 넣기 시작한다. 4까지 하고 중단 했기에, 5 를 넣고 다음으로 6을 넣을 것이다.6을 넣었으니, 찾고자 하는 값인 6임을 인지하게 되고, 다시 이 과정을 반복한다.

 

글로 설명하는 것이 어려웠을 정도로,

느끼기에 난이도가 있는 문제 같았다. 아니면, 다른 더 쉬운 풀이가 있는지도 모르겠다.

rough draft

 

2. 코드

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

public class b1874 {
    public static void main(String[] args) throws IOException{
        Scanner scanner = new Scanner(System.in);

        Stack<Integer> stack_n = new Stack<>();
        Stack<Integer> stack_final = new Stack<>();
        Stack<String> result = new Stack<>();

        int number = Integer.parseInt(scanner.nextLine());
        List<Integer> list = new ArrayList<>();
        int loop = 0;
        int no = -1;

        for(int i=number; i>=1; i--){
            stack_n.push(i);
        }

        for (int i=0; i<number;i++){
            int new_num = Integer.parseInt(scanner.nextLine());
            list.add(new_num);
        }

        int i = 0;

        while(!stack_n.isEmpty()){
            if(!Objects.equals(stack_n.peek(), list.get(i))){
                stack_final.push(stack_n.pop());
                loop +=1;
                result.add("+");
            }
            else{
                stack_final.push(stack_n.pop());
                loop +=1;
                result.add("+");
                while(!stack_final.isEmpty()&&Objects.equals(stack_final.peek(), list.get(i))){
                    stack_final.pop();
                    result.add("-");
                    i++;
                }
            }
            if(loop==number&&!stack_final.isEmpty()){
                System.out.println("NO");
                no = 1;
                break;
            }
        }

        if(no!=1) {
            for(String r: result){
                System.out.println(r);
            }
        }
    }

}