[BOJ 25577] 열 정렬정렬 정

https://www.acmicpc.net/problem/25577

25577번: 열 정렬정렬 정

 

하나의 예를 살펴보자.

 

1 7 2 9 3 8 0

 

이것은 이렇게 정렬되어야 한다.

 

0 1 2 3 7 8 9

 

1이 있는 자리에 0이 있어야 하고, 0이 있는 자리에 9가 있어야 하고, 9가 있는 자리에 3이 있어야 하고, … 그렇다.

 

그러므로 여기서 현재의 상태와, 이것이 어떻게 바뀌어야 하는지 간의 관계에 대한 그래프를 만든다.

각 위치의 (현재 수) -> (원래 그 자리에 있어야 하는 수)들을 edge로 만든다.

여기서는 1->0, 7->1, 2->2, 9->3, 3->7, 8->8, 0->9이다. 

 

그리고 이 그래프에서의 cycle을 찾는다.

1 -> 0 -> 9 -> 3 -> 7 -> 1

2 -> 2

8 -> 8

답은 (cycle의 길이 - 1)의 합.

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    vector<int> arr_sorted = arr;
    sort(arr_sorted.begin(), arr_sorted.end());
    
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        mp[arr_sorted[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = mp[arr[i]];
    }

    int ans = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; ++i) {
        if (visited[i]) {
            continue;
        }

        int cycle_len = 0;
        int cur = i;
        while (!visited[cur]) {
            visited[cur] = true;
            ++cycle_len;
            cur = arr[cur];
        }
        ans += cycle_len - 1;
    }

    cout << ans << kEndl;
}

 

재밌는 문제

 

앞으로는 스터디에서 푼 것들 다 그때그때 풀어둬야겠다. 지난주에 푼 것도 재밌었는데 나중에 풀어야겠다- 하고서는 넘어갔더니 잊어버려서 복기하려면 시간이 걸릴 거 같다.

 

근데 다음 스터디는 무려 10/31이다 ㅋㅋ

 

이렇게 가늘고 길게 가길!

 

 

 

 

 

 

 

https://blog.naver.com/mini_gb/223222623341

[BOJ 25577] 열 정렬정렬 정