[Java] 백준(실버-2) 1874번 - 스택 수열

입출력 예시

Input

8
4
3
6
8
7
5
2
1

Output

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

문제 풀이

---

문제 제목에도 나와있듯이, 자료구조중 하나인 스택(Stack)을 활용해야 한다. 입력값마다 스택에 push 및 pop을 하여 수열을 만들 수 있는지 검증해야 한다.

생각해낸 아이디어는 다음과 같다.

아이디어 도출

1. 1부터 N까지 오름차순으로 임시스택에 저장한다. ex) N=8이면, stack=[8,7,6,5,4,3,2,1]
2. N만큼 반복하며 입력을 받아 임시스택의 맨 위 값과 같을 때까지 꺼내서 새 스택에 집어 넣는다.(push연산)
3. 새스택의 맨 위 값과 입력값이 같다면, 새 스택에서 값을 꺼낸다.(pop연산)
4. 다만, 새스택의 맨 위값과 입력값이 같지 않다면, 수열을 이룰 수 없으므로 NO를 출력해야 한다.

n이 8일 때의 예를 들어보자.

tmp = [8,7,6,5,4,3,2,1] // 임시 스택
st = [] // 새 스택

input(4) <= tmp.peek()=1
    st.push(tmp.pop()) // tmp=[8,7,6,5], st=[1,2,3,4], push연산 4번 수행
    input(4)==st.peek()=4
        st.pop() // st=[1,2,3], pop연산 1번 수행

input(3) <= tmp.peek()=3
    input(3)==st.peek()=3
        st.pop() // st=[1,2], pop연산 1번 수행

input(6) <= tmp.peek()=2
    st.push(tmp.pop()) // tmp=[8,7], st=[1,2,5,6], push연산 2번 수행
    input(6)==st.peek()=6
        st.pop() // st=[1,2,5], pop연산 1번 수행

input(8) <= tmp.peek()=5
    st.push(tmp.pop()) // tmp=[8,7], st=[1,2,5,7,8], push연산 2번 수행
    input(8)==st.peek()=8
        st.pop() // st=[1,2,5,7], pop연산 1번 수행

input(7) <= tmp.peek()=7
    input(7)==st.peek()=7
        st.pop() // st=[1,2,5], pop연산 1번 수행

input(5) <= tmp.peek()=5
    input(5)==st.peek()=5
        st.pop() // st=[1,2], pop연산 1번 수행

이하 생략..

위 로직대로 진행되면 push와 pop 연산별로 ”+,+,+,+,-,-,+,+,-,+,+,-,-,-,-,-“ 를 구할 수 있다.

이제 코드를 작성해보자.

int N = Integer.parseInt(br.readLine());
Stack<Integer> tmp = new Stack<>();
Stack<Integer> st = new Stack<>();
ArrayList<String> operator = new ArrayList<>();
boolean status = true;

for(int i=N; i>=1; i--) {
    tmp.push(i);
}

먼저 N을 입력받고, N을 오름차순으로 담을 임시스택 tmp와 새 스택 st를 초기화한다. 그리고 출력할 연산자 문자열을 담을 operator 리스트를 초기화한다. 마지막으로 수열을 이룰 수 있는지 여부를 확인할 status 변수를 true로 초기화한다.

왜 리스트에 담아 출력하는가?
push와 pop연산이 일어날 때마다 출력을 하게 되면 status가 true임에도 “+”와 “-“ 문자열을 출력할 수 있기에, 별도의 리스트에 담아뒀다가 status의 상태에 따라 출력하기 위함이다.

for(int i=1; i<=N; i++) {
    int input = Integer.parseInt(br.readLine());
    while(!tmp.empty() && tmp.peek() <= input) {
        st.push(tmp.pop());
        operator.add("+");
    }
    if(st.peek() == input) {
        st.pop();
        operator.add("-");
    }
    else status = false;
    
}

이제 위에서 도출한 아이디어대로 코드를 작성했다. 입력값 input과 tmp 맨위 값과 비교하여 push연산을 행하고, st의 맨 위값과 비교하여 pop연산을 수행한다.

if(status==true) {
    for(String op : operator) bw.write(op + "\n");
}
else bw.write("NO"+"\n");

마지막으로 N까지 입력받은 값이 수열을 이룰 수 있다면 operator 리스트의 원소를 출력하고, 수열을 이룰 수 없다면 “NO”를 출력하면 된다.

작성코드

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

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> tmp = new Stack<>();
        Stack<Integer> st = new Stack<>();
        ArrayList<String> operator = new ArrayList<>();
        boolean status = true;

        for(int i=N; i>=1; i--) {
            tmp.push(i);
        }

        for(int i=1; i<=N; i++) {
            int input = Integer.parseInt(br.readLine());
            while(!tmp.empty() && tmp.peek() <= input) {
                st.push(tmp.pop());
                operator.add("+");
            }
            if(st.peek() == input) {
                st.pop();
                operator.add("-");
            }
            else status = false;
            
        }
        if(status==true) {
            for(String op : operator) bw.write(op + "\n");
        }
        else bw.write("NO"+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• EmptyStackException을 고려하여 스택이 비어있는지를 잘 확인해야 했다.