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

백준 문제 풀이: 1849 [순열]

---

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

문제 설명:

길이가 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);
    for (int i = 1; i <= n; i++) {
        int k = arr[i];
        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] << '\n';
    }
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 세그먼트 트리를 활용하여 효율적으로 인덱스를 찾고 업데이트합니다.
• 구현 세부사항:
  • init: 세그먼트 트리를 초기화하며, 각 구간의 길이를 저장합니다.
  • query: 현재 남은 자리에서 주어진 k번째 위치를 찾습니다.
  • update: 특정 위치를 0으로 업데이트하여 사용된 자리를 표시합니다.
• 시간 복잡도: O(n log n)
  • 세그먼트 트리 초기화: O(n)
  • query와 update 연산: O(log n)

---

결과

입력된 배열에 따라 올바른 순열을 출력합니다. 세그먼트 트리를 사용하여 효율적으로 구현되었으며, 시간과 공간 복잡도를 최적화했습니다.

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