[1874] 스택 수열

✔ 스택 수열

[백준 1874]

문제 분석하기

스택의 원리를 정확하게 알고 있는지 묻는 문제

스택의 pop, push 연산과 후입선출 개념을 이해하여 문제에 접근

손으로 풀어보기

1. 1부터 자연수를 증가시키면서 입력으로 주어진 숫자와 비교하여 증가시킨 자연수를 스택에 추가하거나 빼는 방식 이용
2. 현재 수열 값 >= 자연수일 경우
   • 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 스택에 push한 후, 마지막 1회만 pop
3. 현재 수열 값 < 자연수일 경우
   • pop으로 스택에 있는 값을 꺼낸 후, 꺼낸 값이 현재 수열 값이 아니라면 수열을 표현할 수 없게 됨

자연수 1~4		자연수 5~6		자연수 7~8
4 3 2 1	2 1	6 5 2 1	5 2 1	8 7 5 2 1

슈도코드 작성하기

N(수열 개수) A[](수열 배열)
수열 배열 채우기
for(N만큼 반복)
{
    if(현재 수열 값 >= 오름차순 자연수) {
        while(값이 같아질 때까지)
        {
            push()
            (+) 저장
        }
        pop()
        (-) 저장
    }
    else(현재 수열 값 < 오름차순 자연수) {
        pop()
        if(스택 pop 결괏값 > 수열의 수) NO 출력
        else(-) 저장
    }
}
if(NO 값을 출력한 적이 없으면) 저장한 값 출력

코드 구현하기

/**
 * 1874) 스택_수열
 */
public class D011_1874 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(수열 개수)
        int N = sc.nextInt();
        // A[](수열 배열)
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        StringBuffer bf = new StringBuffer();
        // 오름차순 수
        int num = 1;
        boolean result = true;
        for (int i = 0; i < A.length; i++) {
            // 현재 수열의 수
            int su = A[i];
            // 현재 수열 값 >= 오름차순 자연수 : 값이 같아질 때까지 push() 수행
            if (su >= num) {
                while (su >= num) {
                    stack.push(num++);
                    // (+) 저장
                    bf.append("+\n");
                }
                stack.pop();
                // (-) 저장
                bf.append("-\n");
                // 현재 수열 값 < 오름차순 자연수 : pop()을 수행해서 수열 원소를 꺼냄
            } else {
                int n = stack.pop();
                // 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열을 출력할 수 없음
                if (n > su) {
                    System.out.println("NO");
                    result = false;
                    break;
                } else {
                    // (-) 저장
                    bf.append("-\n");
                }
            }
        }
        // if(NO 값을 출력한 적이 없으면) 저장한 값 출력
        if (result)
            System.out.println(bf.toString());
    }
}