[BoJ][JAVA] 1874 - 스택 수열

문제 설명

입출력 예시

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

🔍 리뷰

체감 난이도: ⭐️⭐️⭐️

⭐️ - EZ
⭐️⭐️ - 고민 좀 했다..
⭐️⭐️⭐️ - 못풀었다… 해설 봤음
⭐️⭐️⭐️⭐️ - 해설 봐도 모르겠어
⭐️⭐️⭐️⭐️⭐️ - 이거 어떻게 풀었지 내가..?

문제 이해

이 문제에서는 입력의 분류가 두 가지다.

• 첫째 줄: 수열의 크기 N을 입력,
• 둘쨰 줄부터 ~ N번째 줄: N개의 수열의 요소를 입력한다.

Stack에 1부터 n까지 차례로 각 요소를 push 혹은, pop하여 pop을 한 결과가 수열의 순서와 동일해야 한다.

연산 중에 push를 한다면 ‘+’를 출력하고, pop을 한다면 ‘-’를 출력한다.

만약 어떠한 연산으로도 스택에서 pop한 결과가 수열과 동일할 수 없다면 ‘NO’를 출력한다.

내 코드

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

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));
        int n = Integer.parseInt(br.readLine());

        Stack<Integer> s = new Stack<>(); // Stack
        int current = 1; // 현재 스택에 넣을 숫자 (1부터 시작)
        StringBuilder result = new StringBuilder();

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

            while (current <= target) { // 현재 값이 입력값보다 작거나 같다면 push
                s.push(current);
                result.append("+\\n");
                current++;
            }

            // 스택의 top이 target과 같다면 pop
            if (s.peek() == target) {
                s.pop();
                result.append("-\\n");
            } else { // target을 만들 수 없으면 NO 출력 후 종료
                bw.write("NO\\n");
                bw.flush();
                return;
            }
        }

        // 종료
        bw.write(result.toString());
        bw.flush();
        bw.close();
    }
}

해설

Stack을 S, 수열의 T현재 값을 t라고 한다면,

1. 우선 ‘+’, ‘-’를 저장할 StringBuilder를 생성한다. 이는 반복문에서 출력해버린다면 ‘NO’를 출력해야 할 때, ‘NO’만 출력할 수 없기 때문.
2. 또한, 반복문에서 Stack에 들어 갈 값을 기억할 변수(current)를 선언한다.
3. Stack에 1부터 n까지 채워야 한다 → 반복문 사용
4. 반복문 안에서 수열의 요소를 입력받고 그 값과 현재 값을 비교한다
5. 비교하여 현재 stack에 ‘들어갈’ 값이 작거나 같다면 계속 push해버리고
6. push할 때마다 현재 ‘들어 갈’ 값을 담는 변수(current)를 1 증가시켜준다.
7. stack에 ‘들어 갈’ 값이 입력받은 요소보다 크다면 push를 멈추고
8. stack에서 가장 마지막 값(Last Input)을 입력받은 요소와 비교한다
9. 비교 결과가 일치한다면 pop한다.
10. 첫 번째 pop은 일치할 수밖에 없다. 1부터 n까지 중에 수열에 들어갈 첫 번째 요소와 일치하는 값은 무조건 찾을 수 있기 때문이다.
11. 하지만 아래의 경우는 절대 수열과 만족하는 OutStack을 만들 수 없다.
    1. Stack{ 1, 2, 3, 4, 5} / 수열에 들어갈 요소 입력값: 5 일때 수열을 { 5 }가 되고, 스택에서 아래와 같이 pop해준다.
    2. Stack{1, 2, 3, 4} / OutStack{ 5 } = 수열{ 5 } 인 상황이라 동일해진다
    3. 하지만 그 다음 수열에 들어갈 요소입력이 3이라면?
    4. Stack{1, 2, 3, 4} / OutStack{ 5 } / 수열 { 5, 3 } 이렇게 됐을 경우, 절대로 pop해서 OutStack으로 담는다고 해도 { 5, 4, 3 }이 되지 { 5, 3 }이 될 수 없다는 것을 알 수 있다.
    5. 그러므로 이 경우, else에서 ‘NO’를출력을 해준다.