[코딩테스트] 백준 1874번: 스택 수열 - 예제1 과정 낱낱이 해석

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

✔️ 1874번: 스택 수열 문제

와.. 이게 뭐라고 해석하는 데 몇시간이 걸렸다 ...
구현은 둘째 치고 애초에 문제부터가 이해되지 않아서 더 오래 걸림
저 예제 입력1과 예제 출력1에 나열된 값들의 의미가 너무 헷갈렸다 🤦🏻

검색도 해보고, GPT에도 물어보고, 노트에도 열심히 그려보고 한참 애먹은 끝에 결국 이해했는데
나같은 코딩테스트 초보에게는 이정도 문제도 꽤 어렵다고 느껴졌다.

간신히 이해한(😂) 내용을 잊어버리지 않기 위해 정리해본다.

---

❓ 예제 입력1 의미

예제입력1 값 : 8 4 3 6 8 7 5 2 1

• 여기서 첫번째 값 8은 수열의 길이가 될 숫자고,
  나머지 4 3 6 8 7 5 2 1 은 순서대로 pop을 해야 하는 대상이 된다.

❗ 예제 출력1 의미

예제출력1 값 : + + + + - - + + - + + - - - - -

• 1부터 8까지의 수에 대해 차례로
  [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop]
  연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

---

💻 구현 코드

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();	// 출력할 결과물을 저장할 StringBuilder

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

        // 수열의 길이가 될 숫자를 입력받는다.
        int n = Integer.parseInt(br.readLine());

        int start = 0;

        // n번 반복
        while(n-- > 0) {

            // 수열의 항에 해당하는 정수들을 중복되지 않게 순서대로 입력받는다.
            int value = Integer.parseInt(br.readLine());

            // 1. value가 start보다 큰 경우
            if(value > start) {
                // start + 1부터 입력받은 value 까지 push
                for(int i = start + 1; i <= value; i++) {
                    stack.push(i);
                    sb.append('+').append('\n');    // + 를 sb에 저장
                }
                start = value;  // 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화
            }

            // 2. top에 있는 원소가 입력받은 값과 같지 않은 경우
            else if(stack.peek() != value) {
                System.out.println("NO");
                return;		// 또는 System.exit(0); 으로 대체해도 됨.
            }

            // 3. 입력받은 값(최상단 데이터)을 추출해야 하므로 pop
            stack.pop();
            sb.append('-').append('\n');    // - 를 sb에 저장

        }

        System.out.println(sb);
    }
}

---

📌 예제1 구현 과정 해석

예제입력1 값 : 8 4 3 6 8 7 5 2 1
예제출력1 값 : + + + + - - + + - + + - - - - -

---

• References
  https://st-lab.tistory.com/182

 

---

< 해당 글은 velog에서 이전하며 옮겨온 글로, 가독성이 좋지 않을 수 있는 점 양해 부탁드립니다. >

🔗 velog 버전 보기 : https://velog.io/@ryuneng2/코딩테스트-백준-1874번-스택수열