[백준 java] 1874 - 스택 수열

1874번: 스택 수열

---

문제 푸는시간보다 문제를 이해하는데 좀 걸린 것 같다.

예제 입력의 첫번째 줄 숫자 N은 수열의 길이

두번 째 부터 N+1 번째 줄 까지 숫자는 출력해야하는 수열이다.

 

 

문제풀이

만약 N이 8이 들어온다면 

1 2 3 4 5 6 7 8 순서로 push와 pop을 사용하여 

4 3 6 8 7 5 2 1 을 만들어야한다.

( pop이 출력 )

즉 아래와 같은 순서로 수열이 만들어진다.

1 push [1]
2 push [1,2]
3 push [1,2,3]
4 push [1,2,3,4]
4 pop  [1,2,3] 		4
3 pop  [1,2] 4	 	3
5 push [1,2,5] 		4 3
6 push [1,2,5,6]	4 3
6 pop  [1,2,5]		4 3 6
7 push [1,2,5,7]	4 3 6
8 push [1,2,5,7,8]	4 3 6
8 pop  [1,2,5,7]	4 3 6 8
7 pop  [1,2,5]		4 3 6 8 7
5 pop  [1,2]		4 3 6 8 7 5
2 pop  [1]		4 3 6 8 7 5 2
1 pop  []		4 3 6 8 7 5 2 1

 

해당 수열을 만들기 위해

for문으로 push할 숫자를 정해주었고

while문에서 push한 숫자(제일 위에 있는 숫자)를 peek으로 꺼내본다

 

1. 만약 꺼낸 숫자가 (출력해야하는 숫자) pop 와 같은 경우에는

꺼낸 숫자를 제거하고 다시 제일 위 숫자를 꺼낸다

2. 일치하지 않으면 while문을 벗어난다

 

그리고 계속 for문을통해 숫자를 push

for문이 끝나고 스택에 남은 수가 있으면 수열을 만들지 못한 것이니  "NO"를 출력하고

스택이 비여있으면 저장한 문자열을 출력한다

(자세한 내용은 주석 참고!)

 

---

// 스택 수열
// https://www.acmicpc.net/problem/1874

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

public class B1874 {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();

        N = Integer.parseInt(bf.readLine());
        Stack<Integer> stack = new Stack<>();
        int[] intArr = new int[N];

        for (int i = 0; i < N; i++) {
            intArr[i] = Integer.parseInt(bf.readLine());
        }

        // index 는 수열 배열의 (intArr[index]) 현재 위치를 나타낸다 (삭제해야하는 숫자 위치)
        int index=0;
        // for 문으로 스택에 숫자를 추가하였다
        // 다음 저장할 위치를 i로 기억
        for (int i = 1; i < N+1; i++) {
            stack.push(i);
            sb.append("+").append("\n");

            while(true) {
                // index 가 출력해야하는 수열목록 보다 커지거나
                // stack 의 크기가 0이되면 while 문 빠져나오기
                if(index>N-1) break;
                if(stack.size()==0) break;
                // peek 으로 제일 위 스택 꺼내보기
                int temp = stack.peek();
                if (intArr[index] == temp) {
                    // 만약 꺼낸 숫자가 삭제해야하는 숫자면
                    // 삭제 후 수열 index ++ 해주어 다음순서
                    stack.pop();
                    index++;
                    sb.append("-").append("\n");
                    continue;
                }
                break;
            }
        }
        if(stack.size()==0){
            System.out.println(sb);
        }else{
            System.out.println("NO");
        }
    }
}

 

한번에 성공!