[스택] 백준 - 1874

백준 1874 - 스택 수열

1. 문제 분석

문제 이해

스택의 원리를 정확하게 알고 있는지 확인하는 문제
스택의 pop, push과 후입선출 특성을 이해하고 있다면 쉽게 풀 수 있을 것이다
단, 스택에 push하는 순서는 오름차순을 지키도록 함

에제 입력으로 문제 이해를 해보자

8
4
3
6
8
7
5
2
1

순서대로 입력 했다고 하자

수열 4 찾아야함
STACK - 1
STACK - 1 2
STACK - 1 2 3
STACK - 1 2 3 4 / PUSH(4) 까지
수열 3 찾아야함
STACK - 1 2 3 / POP(3)
수열 6 찾아야함
STACK - 1 2 5 6 / PUSH(6) 까지 한 후 POP(6)
수열 8 찾아야함
STACK - 1 2 5 7 8 / PUSH(8) 까지 한 후 POP(8)
수열 7 찾아야함
STACK - 1 2 5 7 / PUSH(7) 까지 한 후 POP(7)
수열 5 찾아야함
STACK - 1 2 5 / POP(5)
수열 2 찾아야함
STACK - 1 2 / POP(2)
수열 1 찾아야함
STACK - 1 / POP(1)

이러한 방식으로 문제를 풀어야 한다

• 어떻게 스택 연산을 수행할까 (오름차순으로 넣고 뺄까)

  • 현재 수열 값 >= 자연수

    • PUSH(4) 까지 해야하니 자연수가 1부터 4까지 PUSH() 하고 마지막에 한 번 POP()

  • 현재 수열 값 < 자연수

    • POP(4) 를 하면면 자연수는 5가 되고 수열 값은 3이 된다 따라서 POP(3)
    • 만약 해당 조건을 만족하지 않는 다면 스택이 정상적으로 작동하지 않기 때문에 "NO" 출력

입력

• 첫째 줄 - n (1 이상 10만 이하)
• 둘째 줄 - 수열을 이루는 1이상 n이하의 정수
• 중복 되는 정수는 나오지 않는다

출력

• push -> "+" / pop -> "-"
• 불가능한 경우 "NO"

시간 복잡도

• Stack 연산(pop(), push())은 상수 시간 복잡도가 소요된다 -> O(1)
• 최대 한 번씩 스택에 값을 pop, push 하니까 N개의 수를 처리하는데 O(N)의 시간이 걸림

코드 구현

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

public class No_1874 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		int T = Integer.parseInt(br.readLine());
		int arr[] = new int[T];
		
		// 1. 수열 배열 만들기
		for(int i = 0; i < T; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Stack<Integer> stack = new Stack<>();
				
		int num = 1;
		boolean ps = true;
		
		// 2. 수열을 하나씩 확인
		for(int i = 0; i < arr.length; i++) {
			int su = arr[i];
			
			// 3. 수열이 num 보다 크면 num을 수열 숫자까지 push
			if (su >= num) {  
				while(su >= num) {
					stack.push(num++);
					sb.append("+\n");
				}
				stack.pop();
				sb.append("-\n");
			} else {  // 4. 수열이 num 보다 작을 때
				int top = stack.pop(); 
				
				// 5. 스택에서 꺼낸 top와 수열 값이 다른 경우
				if(top != su) {
					System.out.println("NO");
					ps = false;
					break;
				} else {
					sb.append("-\n");
				}
			}
		}
		
		// 6. for문이 중단되지 않고 스택 연산이 모두 이뤄진 경우
		if(ps) {
			System.out.println(sb.toString());
		}
	}
}