[스택] 스택으로 수열 만들기

목차

1. 풀이

(1) 문제 출처

백준 1874번, 스택 수열 : https://www.acmicpc.net/problem/1874

 

핵심 키워드

1) 문제 

• 시간 제한 2초
• 스택 구조를 활용해야 한다.
• 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다
• 스택에 push하는 순서는 반드시 오름차순이다.
• 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지 여부를 확인한다.
  • 수열을 만들 수 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있어야 한다.

 

2) 입력

• 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다.
• 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다
• 같은 정수가 두 번 나오지 않는다.

3) 출력

push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

(2) 풀이

스택을 활용하여 문제 풀이

 

스택(Stack) 

- 스택은 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 후입선출(LIFO: Last-In-First-Out) 리스트다.

- 스택에서 쌓아 올린 데이터의 개수를 표시하기 위해서 일반적으로 top이라는 변수를 사용

- 스택에서 삽입 연산은 push, 삭제 연산은 pop으로 표시한다.

출처 : https://www.programiz.com/dsa/stack

(3) 풀이 적용

1. 입력받은 수열 개수(N)만큼 수열 배열(A)을 생성하고 for문을 통해 입력 받은 수를 차례대로 배열의 값으로 저장한다.
2. 스택 생성, 스택에 push할 오름차수 자연수(num) =  1 로 초기화, 연산결과를 표현하기 위해 StringBuffer 생성
3. 스택으로 수열만들기 핵심코드

for (A.length만큼 반복) {
	int 현재수열값 = A[i]; // 현재 수열값 불러오기
    if (현재수열값 >= 오름차순 자연수 ) {
        while (둘의 값이 같아질 때까지) {
            push();
            (+) 저장;
        }
        pop();
        (-) 저장;
    } else {
        pop()
        if (스택 pop 결과값 > 현재수열의값) {
            NO 출력
            return
        } else {
            (-) 저장
        }
    }
}

2. 정답

(1) Stack 클래스 사용

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();
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int[] s = new int[n];

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

       int index = 1;
       for ( int num : s) {
           if (num >= index) {
               while (num >= index) {
                   stack.push(index++);
                   sb.append("+\n");
               }
               stack.pop();
               sb.append("-\n");
           } else {
               if (stack.pop() > num) {
                   System.out.println("NO");
                   return;
               } else {
                   sb.append("-\n");
               }
           }
       }
        System.out.println(sb);
    }
}

 

(2) ArrayDeque 클래스 사용

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class P1874_스택수열2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수열 개수
        int[] A = new int[N]; // 수열 배열
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        Deque<Integer> stack = new ArrayDeque<>();
        int num = 1;
        StringBuffer bf = new StringBuffer();
        boolean result = true;

        for (int i = 0; i < A.length; i++) {
            int su = A[i];
            if (su >= num) {
                while (su >= num) {
                    stack.push(num++);
                    bf.append("+\n");
                }
                stack.pop();
                bf.append("-\n");
            } else {
                int n = stack.pop();
                if (n > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    bf.append("-\n");
                }
            }
        }
        if (result) {
            System.out.println(bf);
        }
    }
}

- Deque 인터페이스를 구현한 ArrayDeque클래스는 스택과 큐 기능을 둘다 사용할 수 있고, Stack 클래스보다 처리 속도가 빠르다.

- 스택과 큐 관련 자료구조를 활용할 경우 ArrayDeque 클래스를 사용하는 것이 좋다. 

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)

- 알고리즘(이관용&김진욱)