[코딩테스트] 백준 1874 자바

백준 1874

백준 1874 문제

import java.util.*;

public class Boj1874 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 수열의 개수
        int[] arr = new int[n]; // 수열 선언
        Stack<Integer> stack = new Stack<>(); // 빈 스택 생성
        int num = 1; // 시작값
        boolean possible = true; // 스택 구조인지 확인
        StringBuilder sb = new StringBuilder(); // 정답을 답을 StringBuilder

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // 수열 담기
        }

        for (int i = 0; i < arr.length; i++) {
            int e = arr[i]; // 수열에서 값을 꺼닌다.
            if (e >= num) { // 꺼낸 값이 현재의 num값 보다 크거나 같다면
                while (e >= num) { // num값이 꺼낸 값과 크거나 같아질 때까지
                    stack.push(num++); // num값을 스택에 담아주고, num을 1 증가시킨다.
                    sb.append("+\n"); // 그리고 sb에 "+"를 추가한다.
                }
                stack.pop(); // num이 꺼낸 값과 같아졌기 때문에 stack에서 값을 꺼내준다.
                sb.append("-\n"); // sb에 "-"를 추가해준다.
            } else { // num이 꺼낸 값보다 작다면
                int t = stack.pop(); // 스택에서 값을 pop한다.
                if (t != e) { // pop한 값이 수열에서 꺼낸 값과 다르다면
                    System.out.println("NO"); // 스택 구조에 어긋에 나기 때문에 NO를 출력하고
                    possible = false; // 스택 구조가 아니라는 뜻의 possible를 false로 변환한다.
                    break; // 반복문을 중단한다.
                } else {
                    sb.append("-\n"); // pop한 값이 수열에서 꺼낸 값과 같다면, 정답에 "-"를 추가한다.
                }
            }
        }
        if (possible) { // 스택 구조가 올바르다면
            System.out.println(sb); // 정답을 출력한다.
        }
    }
}

풀이

1. 입력된 수열이 스택 구조에 맞는지 확인하는 문제이다.
2. 수열의 개수를 입력받아 n 변수에 담는다.
3. 수열을 담을 수 있는 배열을 n의 크기만큼 선언한다.
4. 스택 구조에 맞는지 확인하기 위해 빈 스택을 생성한다.
5. 오름차순으로 스택에 값을 넣기 때문에 초기값인 num을 1로 초기화한다.
6. 스택의 구조에 올바른지 판단하는 possible 변수를 true로 선언한다.
7. 스택에 값을 push()했는지 pop()을 했는지 기록을 담을 StringBuilder를 sb로 선언한다.
8. n번만큼 루프를 돌면서 수열을 arr 배열에 담는다.
9. 수열을 차례대로 반복한다.
10. 수열의 값을 꺼낸다.
11. 수열에서 꺼낸 값이 현재의 num보다 크거나 같다면, num이 꺼낸 값보다 크거나 같아질 때까지 스택에 push()를 해주면서 num값을 1 증가시키고, sb에 +를 기록해준다.
12. num값이 수열에서 꺼낸 값과 같아졌다면, 스택에서 pop()을 해주고, sb에 -를 기록해준다.
13. 수열에서 꺼낸 값이 num보다 작다면, 우선 스택에서 pop()을 하여 변수 t에 담는다.
14. 수열에서 꺼낸 값과 t값이 다르다면, 스택의 구조에 어긋나기 떄문에 NO를 출력하고, possible를 false로 변환하고, break로 루프를 중단한다.
15. 수열에서 꺼낸 값과 t값이 같다면, sb에 -를 기록한다.
16. 수열을 정상적으로 반복을 완료했으면 스택의 구조에 알맞기 때문에 기록된 sb를 출력한다.