[백준 1874] - [스택] - 스택 수열 (JAVA)

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

---

이문제는 스택의 활용 문제로 보인다. 

스택을 이해하면 풀수 있다! 하는거 같다. 

근데 정답률이 좀 낮은 편이다. 그 이유는 문제가 변태적이기 때문이다. 

솔직히 내가 느끼기에는 변태적이었다. 

일단 이문제를 접근하는 방법은 의외로 간단했다. 

    public static int N;                // 입력받을 수열의 크기
    public static int num = 1;            // 수열을 만들기 위해 1 ~ N가 되는 수
    
    public static int[] arr;            // 입력받을 수열이 저장될 배열
    public static Stack<Integer> stack;    // 수열을 만들기 위해 1 ~ N 까지의 수가 저장될 스택

이문제를 풀기위해 변수는 4개 사용했다. 

N은 수열의 사이즈를 저장하고

N 만큼의 수열을 저장할 배열 arr 을 생성했다. 

수열은 1 ~ N 까지니깐 배열의 크기는 arr = new int[N]; 으로 N 으로 크기를 설정하면 된다.

num 은 문제에 정의된  1 ~ N 까지의 수로 스택에 저장 할 때마다 1씩 증가시켰다. 

num을 스택에 저장하는 조건은 입력받은 수가 num보다 같거나 작을때 현재의 수를 스택에 저장하고 1씩 증가시켰다.

num 은 스택에 넣기 위한 값 이므로 스택에 저장할때 빼고는 사용되는 일은 없다.

중요한건 스택인데 스택에 있는 값을 하나씩 POP() 하면서 수열을 만드는 것이다. 

만약에 만들고자 하는 수가 4 일때

연산은 +, +, +, +, - 이다.

스택에 4까지 PUSH 하고 제일 위에 있는 4를 POP() 한것이다. 

그럼 이어서 3을 출력하고자 한다면?

현재 상태의 num 값은 5다. (4까지 스택에 PUSH 하면서 num을 증가시켰기 때문에)

하지만 3을 출력하고 싶다면 스택에서 3이 나올때까지 POP하면 된다.

전 상태의 이어 연산은 +, +, +, +, -, - 가 된다.

그 다음 6은?

현재 num은 5니깐 PUSH 연산을 두번 해준다 그럼 누적 연산은 +, +, +, +, -, -, +, + 이 된다.

다시 스택에서 꺼내줘야하니깐 POP연산을 한번 한다.

누적 연산은 +, +, +, +, -, -, +, +, - 가 된다.

이쯤에서 중간 점검

num은 7이 돼 있고 

스택에는 1, 2, 5 가 저장돼 있을것이다. 

이제 8을 만들고 싶다면?

스택에 PUSH 연산을 두번 해주고 스택에서 8을 POP 준다.

누적연산 +, +, +, +, -, -, +, +, -, +, +, -

현재 num은 9 니깐 이제 num을 증가시킬 일은 없다.

스택에는 1, 2, 5, 7 이 저장돼 있다

그리고 뽑아 내야 하는 수는 순서대로 7, 5, 2, 1 이다.

그대로 스택에서 POP 연산을 하면서 예제 1번의 답을 출력할 수 있다. 

그럼 예제 2번은 왜 안되는 것일까? 

예제2 에서 만들고 싶은 수열은 1, 2, 5, 3, 4 이다. 

1, 2, 5 까지는 수열을 뽑아낼 수 있지만

이후의 스택의 저장 상태는 {3, 4} 이고 스택은 F-I-L-O 이다 선입 후출 이니깐 스택에서 3을 꺼내게 되면 스택은 비어 있게되고

더이상의 수열 4를 만들수 없기 때문에 예제 2번은 수열을 만들수 없게 되는 것이다. 

예제 1번과 예제 2번을 기반으로 소스를 작성하면 된다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
    public static int N;                // 입력받을 수열의 크기
    public static int num = 1;            // 수열을 만들기 위해 1 ~ N가 되는 수
    
    public static int[] arr;            // 입력받을 수열이 저장될 배열
    public static Stack<Integer> stack;    // 수열을 만들기 위해 1 ~ N 까지의 수가 저장될 스택
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N];
        stack = new Stack<Integer>();
        
        boolean isAble = true;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            
            if(isAble) {
                // num이 arr[i] 보다 작으면 같을때까지 스택에 증가 시키고 num++한다.
                if(num <= arr[i]) {
                    while(num <= arr[i]) {
                        stack.push(num++);
                        sb.append("+ \n");
                    }
                }
                if(stack.isEmpty()) isAble = false;
                else {
                    // 스택의 top이 arr[i]보다 작을때까지 pop 
                    while(stack.peek() >= arr[i]) {
                        stack.pop();
                        sb.append("- \n");
                        if(stack.isEmpty()) {
                            break;
                        }
                    }
                }
            }
        }
        if(isAble) {
            System.out.println(sb.toString());
        }else {
            System.out.println("NO");
        }
    }
}