관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 1874 스택 수열 -스택(stack)- 자바 본문

알고리즘/스택, 큐

[알고리즘] 백준 1874 스택 수열 -스택(stack)- 자바

막무가내막내 2020. 10. 17. 16:29
728x90

www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

 

단계별 풀기 스택 마지막 문제입니다. 

스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자에 유의해야합니다.

 

 

풀이는 다음과 같습니다.

[Java]

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

public class Main {
    private static Stack<Integer> stack = new Stack<>();
    private static int num = 1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int current = sc.nextInt();
            if (num <= current) { //아직 스택에 없는 상태이므로 해당값(current)까지 스택에 숫자를(num) 차례대로 push 해준 뒤 pop()
                while (num <= current) {
                    sb.append("+\n");
                    stack.push(num++);
                }
                sb.append("-\n");
                stack.pop();
            } else { //해당 해당값이(current) 현재 값보다 크면 그 값은 스택에 들어가있는상태
                int n = stack.pop();
                if (n == current) { //스택 가장 상단 값이 해당 값이어야함(순서대로 스택에쌓여있고 두번빼서 가져오면 안되므로)
                    sb.append("-\n");
                } else {
                    System.out.println("NO");
                    return;
                }
            }
        }
        System.out.println(sb.toString());
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다.

728x90
Comments