백준 1777번 [순열복원](C++)-yes6686- 티스토리

백준 문제 풀이: 1777 [순열복원]

---

문제 링크: https://www.acmicpc.net/problem/1777

문제 설명:

길이가 n인 순열이 주어질 때, 순열을 복원하는 문제입니다. 주어진 입력은 각 순열의 원소가 올바른 위치에 들어가기 위해 필요한 남은 빈자리의 개수를 의미합니다. 세그먼트 트리를 사용하여 효율적으로 순열을 복원합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[100001];
int ans[100001];
int tree[400001];

int init(int n, int s, int e) {
    if (s == e) {
        return tree[n] = 1;
    }
    return tree[n] = init(2 * n, s, (s + e) / 2) + init(2 * n + 1, (s + e) / 2 + 1, e);
}

int query(int n, int s, int e, int k) {
    if (s == e) {
        return s;
    }
    if (tree[2 * n] >= k) {
        return query(2 * n, s, (s + e) / 2, k);
    } else {
        return query(2 * n + 1, (s + e) / 2 + 1, e, k - tree[2 * n]);
    }
}

void update(int n, int s, int e, int i, int v) {
    if (i < s || e < i) return;
    if (s == e) {
        tree[n] = v;
        return;
    } else {
        update(2 * n, s, (s + e) / 2, i, v);
        update(2 * n + 1, (s + e) / 2 + 1, e, i, v);
        tree[n] = tree[2 * n] + tree[2 * n + 1];
    }
}

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    init(1, 0, n - 1);
    int s = 0;
    for (int i = n; i >= 1; i--) {
        int k = n - arr[i] - s;
        s++;
        ans[query(1, 0, n - 1, k) + 1] = i;
        update(1, 0, n - 1, query(1, 0, n - 1, k), 0);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 사용하여 현재 남아 있는 빈자리의 상태를 관리하며, 각 숫자의 위치를 계산합니다.
• 구현 세부사항:
  • init: 세그먼트 트리를 초기화하며, 각 구간에 존재하는 빈자리 수를 설정합니다.
  • query: k번째 빈자리를 탐색하여 해당 인덱스를 반환합니다.
  • update: 특정 빈자리를 차지했음을 표시하기 위해 해당 구간의 값을 업데이트합니다.
• 시간 복잡도: O(n log n)
  • 세그먼트 트리 초기화: O(n)
  • query와 update 연산: O(log n)

---

결과

입력된 데이터를 기반으로 복원된 순열을 출력합니다. 세그먼트 트리를 사용하여 효율적으로 빈자리를 관리하였으며, 최적화된 시간 복잡도를 갖습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!