[JAVA/1874번] 스택 수열

문제

입력 및 출력

풀이

import java.io.*;
import java.util.*;

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] resultArray = new int[N];
        for (int i = 0; i < N; i++) {
            resultArray[i] = Integer.parseInt(br.readLine());
        }

        StringBuilder sb = new StringBuilder();
        boolean flag = false;

        int index = 0;
        Stack < Integer > stack = new Stack < > ();
        for (int i = 0; i < N; i++) {
            for (int j = index; j < resultArray[i]; j++) {
                if (stack.isEmpty()) {
                    stack.push(j + 1);
                    sb.append("+").append("\n");
                    index++;
                } else if (stack.peek() != resultArray[i]) {
                    stack.push(j + 1);
                    sb.append("+").append("\n");
                    index++;
                }
            }

            if (stack.peek() == resultArray[i]) {
                stack.pop();
                sb.append("-").append("\n");
            } else {
                flag = true;
                break;
            }
        }
        if (flag == true) {
            System.out.println("NO");
        } else {
            System.out.print(sb.toString());
        }
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법

• 문제 이름이 스택 수열인 만큼 스택을 사용하여 문제를 해결하는 것이 포인트이다.

• 사용자로부터 N개의 숫자를 입력받고, 각 숫자는 1~N까지의 숫자로 구성되어 있으며 숫자 간 중복될 수 없다.

• 이중 반복문을 통해 문제를 해결하였고, 첫 번째 반복문은 0부터 N까지의 반복 조건을 갖는 반복문이고 두 번째 반복문은 index(초깃값: 0)의 값부터 resultArray의 i번째 존재하는 값까지의 반복 조건을 갖는 반복문이다.

• 첫 번째 예제를 예시로 들어보면, resultArray[0] 값은 4이기 때문에 0부터 4까지의 반복 횟수를 갖는 반복문이다.

  반복문 내부는 조건문을 사용하여 두 가지 케이스로 구분하였는데, 첫 번째의 경우 스택이 비어있다면 j의 값에 1을 더하여 스택에 PUSH 연산을 수행하였다. 하지만 실제로 출력해야 하는 값은 "+" 혹은 "-"이므로 StringBuilder를 통해 PUSH 될 경우 "+" POP일 경우 "-"를 APPEND 해주었다.

  두 번째 조건문의 경우 스택의 TOP이 resultArray의 i번째 존재하는 값과 일치하지 않는다면 위와 마찬가지로 처리하였다. 각 PUSH 연산이 한번 일어날 때마다, index의 값을 1씩 증가 처리하였다.

• 위의 반복문을 수행한 후 조건문을 통해 STACK의 TOP 위치에 존재하는 값과 resultArray의 i번째 값을 비교하여 같을 경우 POP 연산을 수행하고, StringBuilder에 "-"를 APPEND 해주었다.

  flag는 사용자가 입력받은 수열을 표현할 수 없을 때, flag의 값을 TRUE로 처리하였고 반복문을 빠져나왔다.