[백준 - 1874] 스택 수열

https://www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

입력

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

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1 

8
4
3
6
8
7
5
2
1

예제 출력 1 

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2 

5
1
2
5
3
4

예제 출력 2 

NO

 

 

Solution

 

 

<문제 이해>

처음에 예시를 이해 못해서 직접 그리면서 풀었다.

예시를 보면 입력받은 숫자 배열이 스택에서 pop의 결과로 나와야하는 배열이다.

즉, 입력받은 대로 pop해야 한다. 만약 이게 안되면 no를 출력한다.

이게 이해가 안돼서 결과를 몇번이나 봤는지 모르겠다....

 

먼저 n번 동안 돌면서 검사를 해야한다.

만약 원하는 숫자가 now(현재 숫자)보다 크거나 같으면 같아질 때까지 now++를 push해주고 +를 문자열 버퍼에 넣는다.

조건에 따라 출력할 문자가 달라 스트링 버퍼를 사용했다.

만약 원하는 숫자와 now가 같아지면 pop하고 -를 넣는다.

 

만약 원하는 숫자가 now보다 작으면 pop을 하는데 이때 pop한 값이 원하는 값보다 크면 만족하지 않으므로  no를 출력한다. 그렇지 않으면 만족하는 것이라 -를 추가한다.

 

 

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

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        //// 수열의 길이 n 입력
        int n = sc.nextInt();

        //입력받은 숫자들 저장
        int[] nums = new int[n];

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

        Stack<Integer> st = new Stack<>();
        // 스택 연산 기록을 위한 문자열 버퍼
        StringBuffer sb = new StringBuffer();
        int now = 1;// 현재 스택에 넣을 숫자 초기화
        boolean answer = true;

        for(int i = 0; i < n; i++) {
            int su = nums[i]; // 현재 처리 중인 수열의 숫자
            if(su >= now){// 현재 숫자가 현재 스택에 넣을 숫자보다 크거나 같은 동안 반복
                while(su >= now){
                    st.push(now++);
                    sb.append("+\n");
                }
                st.pop();// 스택에서 숫자를 꺼냄 (현재 수열의 숫자를 맞추기 위해)
                sb.append("-\n");
            } else {
                int num = st.pop();
                if(su < num) {// 스택에서 꺼낸 숫자가 현재 수열의 숫자보다 크다면
                    System.out.println("NO");// 수열을 오름차순으로 정렬할 수 없음을 출력
                    answer = false;
                    break;
                } else{
                    sb.append("-\n");
                }
            }
        }
        if(answer){System.out.println(sb.toString());} // 수열을 정렬할 수 있는 경우
    }
}