[BOJ/Java] 스택 수열 (1874)

스택 수열 (1874)

1. 문제 분석

문제 개요

• 주어진 정수 순서를 스택을 사용해 수열을 생성하고, 그 수열을 만족하기 위해 필요한 스택 연산(+와 -)을 출력하는 문제이다.
• 수열이 스택을 통해 만들 수 없는 경우에는 "NO"를 출력해야 한다.

입력 형식

• 첫 줄에 정수 n이 주어진다.
• 다음 n줄에 정수가 주어진다. 각 정수는 스택에서 꺼내야 할 순서이다.

출력 형식

• 수열을 생성하기 위한 스택 연산을 +와 -로 출력하고, 스택으로 수열을 만들 수 없는 경우에는 "NO"를 출력한다.

2. 알고리즘 종류

이 문제는 스택을 이용한 시뮬레이션 문제로, 주어진 수열을 스택 연산으로 생성할 수 있는지를 확인하는 방식으로 해결할 수 있다.

3. 주요 부분 및 코드 작성 방법

1. 스택 사용 및 연산 처리

• 정수를 스택에 넣기 위해 + 연산을 기록하고, 꺼내기 위해 - 연산을 기록한다.
• 수열을 만들 수 없는 경우에는 "NO"를 출력한다.

2. 스택 연산 검토

• 주어진 정수를 스택에서 꺼낼 수 있는지 확인하고, 연산을 적절히 기록한다.

4. 코드 설명

메인 함수 (main)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringBuilder sb = new StringBuilder(); // 결과를 저장하기 위한 StringBuilder 객체 생성
        Stack<Integer> stack = new Stack<>(); // 정수형 스택 생성

        int n = Integer.valueOf(br.readLine()); // 정수 n을 입력받음
        int addNum; // 추가할 정수
        boolean check = false; // 수열을 만들 수 있는지 여부를 체크하는 플래그
        int a = 1; // 스택에 넣을 초기 값

        for (int i = 1; i <= n; i++) { // 입력된 정수의 개수만큼 반복
            addNum = Integer.valueOf(br.readLine()); // 현재 처리할 정수를 입력받음

            // 현재 정수 addNum까지 스택에 값 추가
            for (; a <= addNum; a++) {
                stack.push(a); // 스택에 추가할 정수
                sb.append("+").append("\n"); // 스택에 추가하는 연산 기록
            }

            // 스택의 최상단이 addNum과 같다면 스택에서 제거
            if (stack.peek().equals(addNum)) {
                stack.pop(); // 스택에서 정수 제거
                sb.append("-").append("\n"); // 스택에서 제거하는 연산 기록
            } else {
                check = true; // 수열을 만들 수 없음
            }
        }

        // 수열을 만들 수 없는 경우에는 "NO" 출력
        if (!check) {
            System.out.print(sb); // 결과 출력
        } else {
            System.out.print("NO"); // 수열을 만들 수 없음을 출력
        }
    }
}

5. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringBuilder sb = new StringBuilder(); // 결과를 저장하기 위한 StringBuilder 객체 생성
        Stack<Integer> stack = new Stack<>(); // 정수형 스택 생성

        int n = Integer.valueOf(br.readLine()); // 정수 n을 입력받음
        int addNum; // 추가할 정수
        boolean check = false; // 수열을 만들 수 있는지 여부를 체크하는 플래그
        int a = 1; // 스택에 넣을 초기 값

        for (int i = 1; i <= n; i++) { // 입력된 정수의 개수만큼 반복
            addNum = Integer.valueOf(br.readLine()); // 현재 처리할 정수를 입력받음

            // 현재 정수 addNum까지 스택에 값 추가
            for (; a <= addNum; a++) {
                stack.push(a); // 스택에 추가할 정수
                sb.append("+").append("\n"); // 스택에 추가하는 연산 기록
            }

            // 스택의 최상단이 addNum과 같다면 스택에서 제거
            if (stack.peek().equals(addNum)) {
                stack.pop(); // 스택에서 정수 제거
                sb.append("-").append("\n"); // 스택에서 제거하는 연산 기록
            } else {
                check = true; // 수열을 만들 수 없음
            }
        }

        // 수열을 만들 수 없는 경우에는 "NO" 출력
        if (!check) {
            System.out.print(sb); // 결과 출력
        } else {
            System.out.print("NO"); // 수열을 만들 수 없음을 출력
        }
    }
}