[Baekjoon] 1874 - 스택 수열

📝 문제

 

 

🔑 풀이 과정

· 일단 문제를 똑바로, 꼼꼼하게 읽자. 수열을 못 만들면 "NO"를 출력하랬는데, 왜 "No"를 출력시켜서 오답을 받았을까...

 

· n줄에 걸쳐져서 n개의 수가 차례로 들어오는데, 이때 들어오는 수의 의미가 "이 수를 pop 하라" 라는 뜻이다. 만약 이 수를 pop하지 못한다면? NO를 출력하라는 뜻

 

· pushNum이라는 변수를 선언한다. 이 변수는 "현재 스택에 들어와야 하는 수"를 의미한다. 즉, 스택이 처음 생성되면 1부터 들어가야 하므로 처음에는 1로 초기화가 된다. 만약 pushNum이 3이면, 현재 스택에 1, 2가 들어와 있다는 뜻이다.

 

· n줄에 걸쳐서 n개의 수가 들어오는데, 이때 들어오는 수를 m이라고 하자.

① m >= pushNum 일 때,

→ m을 pop해야 하는데, m은 아직 스택에 들어와 있지 않다.

pushNum이 m보다 커질 때 까지 stack에 push 연산을 한다. 그리고 push연산을 할때는 "+"를 출력한다.

② m < pushNum 일 때,

→ m을 pop해야 하는데. m은 이미 스택에 들어있다.

stack.pop()을 한 값이 m이면 pop 된 상황이므로 "-" 출력

stack.pop()을 한 값이 m이 아니라면 수열 생성 불가 상황이므로 "NO"를 출력

 

· 사람들이 StringBuilder를 쓰는 걸 보고 언젠가 써봐야지 했는데 이 문제를 통해 쓰게됐다.

처음엔 그냥 bw.write("+" + "\n")이런식으로 push, pop이 일어날때마다 버퍼에 작성해줬는데, 이럴경우 수열이 완성되지 않을 때도 버퍼 작성된 값이 출력되는 것이었다. 나중에 검색해보니 bw.write()는 최대한 작성할 용도로 쓰고, 저장할 용도로는 쓰지 않는게 좋다고 한다.

 

 

🔓 답안

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));
        StringBuilder sb = new StringBuilder();

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

        //입력 받기
        int n = Integer.parseInt(br.readLine());

        int pushNum = 1; //현재 들어와야 할 숫자를 의미
        boolean isAvailable = true; //수열이 가능한 지를 의미하는 변수
        for(int i = 0; i < n; i++){
            int item = Integer.parseInt(br.readLine());

            if(item >= pushNum){ //item을 pop해야 하는데, 아직 item은 스택에 들어있지 않다.
                while(item >= pushNum){
                    stack.push(pushNum);
                    sb.append("+").append("\n");
                    pushNum++;
                }

                stack.pop();
                sb.append("-").append("\n");
            } else if(item < pushNum){ //item을 pop해야 하는데, item은 이미 스택에 있는 상태.
                if(stack.pop() == item){
                    sb.append("-").append("\n");
                } else{
                    isAvailable = false;
                    break;
                }
            }
        }

        if(isAvailable){
            bw.write(sb.toString());
        } else{
            bw.write("NO");
        }

        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 스택