[백준 온라인저지]스택 수열 - 스택

스택 수열

이번 포스팅 문제는 1874번 문제입니다.

문제요약

문제에서는 수열이 주어지는데 이 수열을 스택으로 만들 수 있는지 없는지를 판단하는 문제입니다. 

예를 들어 {4, 3, 6, 8, 7, 5, 2, 1} 수열이 주어지고 스택에 삽입하는 수는 1부터 순차적으로 증가될 때 이 수열이 스택을 이용해서 어떻게 만들어지는지 알아보도록 하겠습니다.

풀이전략

1. 수열원소 > 자연수라면 "자연수 == 원소"일 때 까지  스택에 push() 합니다
2. 수열원소 < 자연수라면 이미 스택에 수열원소가 들어가 있다는 뜻입니다. 그럼 스택에서 pop()을 수행하여 수열원소를 찾습니다.
   하지만 이 때 "pop()에서 얻은 값이 != 수열원소"라면 해당 수열은 스택으로 만들 수 없는 수열을 뜻합니다. 왜냐하면 스택은 LIFO 구조이기 때문에 최상단 아래 원소를 구할 수 없기 때문입니다.

구현하기

package BackJoon.스택;
 
import java.util.Scanner;
import java.util.Stack;
 
public class _1874_스택수열 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        int[] arr = new int[T];
        for(int i=0; i<T; i++) {
            arr[i] = sc.nextInt();
        }
        
        String s = getSolution(arr);
        System.out.println(s);
    }
    
    private static String getSolution(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();
        int num = 1; // 자연수
        for(int i=0; i<arr.length; i++) {
            int e = arr[i]; // 만들어야 하는 수열요소
            
            // 자연수가 만들어야하는 요소보다 작을 때
            if(num <= e) {
                while(num <= e) {
                    // 자연수를 증가시키며 스택에 추가
                    stack.push(num++);
                    bf.append("+\n");
                    
                    // 만들어야하는 요소까지 스택에 담았다면 꺼냄
                    if(num > e) {
                        stack.pop();
                        bf.append("-\n");
                    }
                }
            } 
            // 자연수가 만들어야하는 요소보다 클 때 -> 만들어야하는 요소는 이미 스택에 들어있다는 의미
            else {
                int n = stack.pop();
                // 스택의 가장 위의 수(n)가 만들어야하는 요소(e)보다 크다면 pop() 을 했을 때 n이 출력되므로 요소를 출력할 수 없음
                if(n > e) {
                    return "NO";
                } //  
                else {
                    bf.append("-\n");
                }
            }
        }
        return bf.toString();
    }
}
 

배운점

알고리즘을 생각하는 것보다 알고리즘을 코드로 옮기는게 역시나 훨씬 어려웠습니다. 전반적인 알고리즘을 구현해놓고 제약사항(인덱스의 마지막 등)을 상세하게 구현해주는게 문제 푸는게 좀 더 수월한 것 같습니다