[JAVA / 자바] 백준 1874번 - 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

---

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

---

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

---

 

---

문제 접근 방법

이번 문제의 수열을 이해하는데 나는 시간이 꽤 오래 걸렸던 것 같다.

스택의 push, pop을 이용하여 입력이 들어온 대로 수열을 만들 수 있는지 물어보는 문제이다.

이때, 스택에 push 하는 수는 1부터 시작해서 push를 할 때마다 그 수는 1씩 증가한다. 수열은 스택에서 pop 했을 때 리턴 값으로 수열이 생성된다.

그렇다면, 다음과 같이 생각해 볼 수 있다.

수열의 입력이 하나씩 들어오면 수열은 스택에서 pop 해서 리턴 값으로 만드는 것이므로

i) 현재 다음 push 할 수가 입력보다 적으면 입력값까지 계속 push를 해주고,

ii) 현재 다음 push 할 수가 입력과 같으면 바로 pop연산을 해주어 수열을 만들어 주고,

iii) 현재 다음 push 할 수과 입력보다 크면 pop연산을 해주어

    - 1) 만약 스택이 입력과 같은 값을 리턴해 주면 다음 입력을 계속 받아 위 조건 i)~iii)에 맞게 반복한다.

    - 2) 만약 스택이 입력과 다른 값을 리턴해 주면 수열 만들기를 중단하고 "NO"를 출력해준다.

 

여기서 주의할 점은 출력으로 입력된 수열을 스택으로 만들 수 있으면 push는 "+", pop은 "-"로 한 줄씩 출력하라고 되어있고, 스택을 만들 수 없으면 "NO"만 출력하라고 되어있다. 그래서 스택 연산할 때마다 바로바로 출력을 해준다면 수열을 만들 수 있는지 없는지는 스택 연산을 하는 도중에 알 수 있기 때문에 문제에서 원하는 결괏값과 달라지게 되므로, StringBuilder를 사용하여 push, pop연산을 각각 +, -로 저장해 두었다가 수열을 만들 수 있다면 StringBuilder로 만든 문자열을 출력하고, 아니면 그냥 "NO"만 출력하게 할 것이다.

그럼 다음 내용을 코드로 아래와 같이 만들어 보겠다.

---

JAVA 코드 풀이

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

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> stack = new Stack<>();
        int order[] = new int[n];
        int input;
        for(int i=0; i<n; i++)
            order[i] = Integer.parseInt(br.readLine());
        int idx = 0;
        int num = 0;
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        while(idx < n){
            while(num < order[idx]) {
                stack.push(++num);
                sb.append("+");
            }
            if(stack.peek() == order[idx]) {
                stack.pop();
                sb.append("-");
            }
            else {
                flag = true;
                break;
            }
            idx++;
        }
        if(flag)
            System.out.println("NO");
        else
            for(int i=0; i<sb.length(); i++)
                bw.write(sb.substring(i, i+1)+"\n");
        bw.close();
    }
}

코드 실행 결과

---

후기

이번 문제는 상대적으로 문제를 이해하는데 많은 시간이 걸렸고, 많은 생각을 했던 것 같다. 이렇게 문제가 이해가 안 될 때 '만약 이게 시험이라면 어땠을까'라는 아찔한 생각이 든다. 문제 이해능력은 어떻게 늘려야 할지 잘 모르겠다,, 문제를 많이 풀면 비슷한 유형들이 보여 문제 이해하는데 지금보다 더 나아질까?라는 생각도 해보는데 아직 문제를 꾸준히 풀기 시작한 지 몇 달 안돼서 그 정도까진 아닌 것 같다. 앞으로 문제를 더 많이 풀어보고 고민도 많이 해보면서 감을 익히도록 해야겠다.

---

문제 원본

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