[백준] 1874번 : 스택 수열 - 자바[Java]

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

1874번: 스택 수열

풀이

스택을 사용하고, 입력받는 숫자를 총 3가지 경우로 나누어 처리한다.

1) 현재 top에 있는 숫자가 입력받은 숫자보다 작으면 그 숫자까지 push하고, 한 번만 pop한다.

ex) 4
1 push, 2 push, 3 push, 4 push, 4 pop

 

2) 현재 top에 있는 숫자가 입력받은 숫자와 같으면 한 번만 pop한다.

ex) 4 3
1 push, 2 push, 3 push, 4 push, 4 pop, 3 pop

 

3) 현재 top에 있는 숫자가 입력받은 숫자보다 크면 그 숫자까지 pop한다.

ex) 4 2
1 push, 2 push, 3 push, 4 push, 4 pop, 3 pop, 2 pop

 

이 때 스택 수열을 만들 수 없는 경우는 다음과 같다.

ex) 5 3 4
1 push, 2 push, 3 push, 4 push, 5 push, 5 pop 4 pop, 3 pop, ?

현재 top에 있는 숫자가 입력받은 숫자보다 커서 pop 연산을 수행할 때, pop하는 숫자가 아직 스택 수열에서 나오지 않았다면 그 스택 수열은 만들 수 없는 스택 수열이다.

 

로직

1. 출력할 문자열을 저장할 StringBuilder sb를 선언하고, n을 입력받는다.

2. n+1 크기의 boolean 형 flag 배열을 선언한다. flag는 스택 수열에서 현재 숫자가 입력으로 들어왔는지를 체크하여 만들 수 있는 스택 수열인지 판단할 때 사용한다.

3. boolean형 변수 no를 선언한다. 이후 숫자를 입력받을 때마다 스택 수열을 만들 수 있는지 체크하여 만약 만들 수 없다면 no를 true로 변경한다.

4. Stack<Integer> st를 선언하고, 0을 push한다. 0을 push하는 이유는 빈 스택일 때 st.peek()를 하면 java.util.EmptyStackException이 발생하기 때문이다.

5. 수열의 숫자를 입력받을 때마다 아래의 3가지 경우로 나누어 로직을 수행한다. 이 때 no == true라면 숫자만 입력받고 아래 로직을 수행하지 않는다.

• 현재 top에 있는 숫자가 입력받은 숫자보다 작으면 그 숫자까지 push하고, 한 번만 pop한다.
• 현재 top에 있는 숫자가 입력받은 숫자와 같으면 한 번만 pop한다.
• 현재 top에 있는 숫자가 입력받은 숫자보다 크면 그 숫자까지 pop한다. 이 때 pop하는 숫자가 아직 스택 수열에서 나오지 않았다면, 스택 수열을 만들 수 없으므로 no를 true로 변경한다.
• num을 입력받았으므로 flag[num] 은 true로 변경한다.

6. no가 true라면 "NO"를 출력하고, 아니면 sb를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        boolean[] flag = new boolean[n+1]; // 해당 숫자가 입력으로 들어왔으면 true 아니면 false
        boolean no = false; // 입력한 스택 수열을 만들 수 없으면 true

        Stack<Integer> st = new Stack<>();
        st.push(0); // st.peek()를 수행할 때 예외 발생하는 것을 방지하기 위해 0을 미리 push

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if (no) continue;

            // 스택의 top에 있는 숫자가 입력한 숫자보다 작으면 push
            if (st.peek() < num) {
                for (int j = st.peek() + 1 ; j <= num; j++) {
                    if (!flag[j]) {
                        st.push(j);
                        sb.append("+\n");
                    }
                }
                // 입력한 숫자 pop
                st.pop();
                sb.append("-\n");
            }
            // 스택의 top에 있는 숫자가 입력한 숫자와 같으면 그 숫자를 pop
            else if (st.peek() == num) {
                st.pop();
                sb.append("-\n");
            }
            // 스택의 top에 있는 숫자가 입력한 숫자보다 작으면 pop
            else {
                for (int j = st.peek(); j > num; j--) {
                    // 아직 입력으로 들어오지 않은 숫자를 pop해야 한다면 해당 스택 수열을 만들지 못한다
                    if (!flag[j]) {
                        no = true;
                        break;
                    }
                    st.pop();
                    sb.append("-\n");
                }
                st.pop();
                sb.append("-\n");
            }

            flag[num] = true;
        }

        if (no) System.out.println("NO");
        else System.out.println(sb);

    }
}

다른 풀이

스택 수열을 만들 수 없는 경우는

현재 top에 있는 숫자가 입력받은 숫자보다 커서 pop 연산을 수행할 때, pop하는 숫자가 아직 스택 수열에서 나오지 않은 경우다.

즉, 현재 top에 있는 숫자가 입력받은 숫자보다 크면, 아직 나오지 않은 숫자를 pop해야 하기 때문에 무조건 만들 수 없는 스택 수열이므로, 이 경우는 아예 for문을 수행할 것도 없이 무조건 NO를 출력하면 된다.

 

수정한 부분

1. 어디까지 입력 받았는지를 알기 위한 변수 start를 추가하여, push 연산을 수행할 때 start를 value 값으로 초기화한다.

2. 입력받은 숫자(num)가 가장 최근에 push한 숫자(start)보다 작은 경우, 입력받은 숫자(num)가 스택의 top에 있는 숫자(st.peek())와 다르면 만들 수 없는 스택 수열이므로 NO를 출력하고 바로 프로그램을 종료한다.

3. 스택 수열에서 현재 숫자가 입력으로 들어왔는지를 체크하는 flag배열과 no 변수가 필요없다.

import java.io.*;
import java.util.*;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        Stack<Integer> st = new Stack<>();
        int start = 0;

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            // 입력한 숫자가 가장 최근까지 push한 숫자보다 크면 push
            if (start < num) {
                for (int j = start + 1 ; j <= num; j++) {
                    st.push(j);
                    sb.append("+\n");
                }
                start = num;
            }
            // 입력한 숫자가 스택의 top에 있는 숫자와 다르면 만들 수 없는 스택 수열
            else if (st.peek() != num){
                System.out.println("NO");
                return;
            }
            // 입력한 숫자 pop
            st.pop();
            sb.append("-\n");
        }

        System.out.println(sb);

    }
}

참고: https://st-lab.tistory.com/182

 

2번째 방법이 메모리와 시간 측면에서 성능이 더 좋은 코드인 것을 확인할 수 있다.