[백준] 1874_스택 수열 - JAVA

백준_1874

1874번: 스택 수열

 

스택(Stack)

삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out)으로 이루어진 자료구조이다. 후입선출은 산입과 삭제가 한 쪽에서만 이루어진다. 

스택 용어

• top : 삽입과 삭제가 일어나는 위치
• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

스택은 깊이 우선 탐색(DFS : Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이다.

후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통한다.

 

코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

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

        int num = 1;

        for(int i = 0; i < n; i++) {
            int su = arr[i];
            if(su >= num) {
                while(su >= num) {
                    stack.push(num++);
                    sb.append("+\n");
                }
                stack.pop();
                sb.append("-\n");
            }
            else {
                int top = stack.pop();
                if(top >  su) {
                    System.out.println("NO");
                    return;
                }
                else {
                    sb.append("-\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

스택이란 자료구조를 잘 이해하고, 사용할 줄 안다면 나름 쉽게 풀리는 문제이다..!

 

 

제출 결과