[BaekJoon] 35309번 - 잘 정의된 들여쓰기 [Java][C++]

문제 링크

---

1. 문제 풀이

들여쓰기 규칙에 맞게 주어진 수열을 배치할 수 있는지 찾는 문제로 들여쓰기는 같은 레벨에 이전 수가 존재하기 않으면 1, 이전 수가 존재하는데 그 후 더 적은 레벨이 존재하면 1, 더 적은 레벨이 존재하지 않으면 해당 수의 다음 수를 적는다. 스택 자료구조를 활용해서 현재 수가 1이면 다음 레벨의 첫 수로 적고 1이 아닐 경우 이전 수가 존재하며 현재 수보다 1 작으면 같은 레벨에 이어서 적고 이전 수가 존재하며 현재 수보다 1 작은 수가 아니면 현재 수가 들어갈 위치가 있는지 찾으면 된다. 현재 수가 들어갈 위치가 없으면 불가능한 경우이다.

아래 예시를 통해 로직을 구성할 수 있었다.

input

1
12
1 2 3 4 1 1 1 2 1 1 3 5

output

YES

예시

1
2
3
4
  1
    1
      1
      2
        1
          1
      3
5

---

2. 코드

1. 풀이 [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        out:
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            int[] arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            Deque<Integer> stack = new ArrayDeque<>();
            for (int x : arr) {
                if (x == 1 || (!stack.isEmpty() && stack.peek() + 1 == x)) {
                    stack.push(x);
                } else {
                    while (!stack.isEmpty() && stack.peek() + 1 != x) {
                        while (!stack.isEmpty() && stack.peek() != 1) {
                            stack.pop();
                        }
                        stack.pop();
                    }

                    if (stack.isEmpty() || stack.peek() + 1 != x) {
                        bw.write("NO\n");
                        continue out;
                    } else {
                        stack.push(x);
                    }
                }
            }

            bw.write("YES\n");
        }

        bw.flush();
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> v(n);
        for (int& x : v) cin >> x;

        stack<int> st;
        bool flag = false;

        for (int x : v) {
            if (x == 1 || (!st.empty() && st.top() + 1 == x)) {
                st.push(x);
            } else {
                while (!st.empty() && st.top() + 1 != x) {
                    while (!st.empty() && st.top() != 1) {
                        st.pop();
                    }
                    st.pop();
                }

                if (st.empty() || st.top() + 1 != x) {
                    cout << "NO\n";
                    flag = true;
                } else {
                    st.push(x);
                }
            }

            if (flag) break;
        }

        if (flag) continue;

        cout << "YES\n";
    }
}

---