백준 18869번 [멀티버스 Ⅱ](C++) -yes6686- 티스토리

백준 문제 풀이: 18869 (멀티버스 II)

---

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

문제 설명:

여러 개의 차원이 존재하는 공간에서 m개의 차원 데이터를 주어진 순서에 따라 정렬했을 때, 동일한 상대적 순서를 가진 차원 쌍의 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

pair<int, int> arr[10001]; // 값과 인덱스를 저장
map<string, int> mp;       // 상대적 순서를 문자열로 저장하는 map

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

    int m, n; // m: 차원의 수, n: 각 차원의 데이터 수
    cin >> m >> n;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[j].first;
            arr[j].second = j + 1; // 원래 인덱스를 저장
        }

        sort(arr, arr + n); // 상대적 순서를 정렬
        string s = "";

        for (int j = 0; j < n; j++) {
            s += to_string(arr[j].second); // 상대적 순서를 문자열로 변환
        }

        mp[s]++; // 같은 상대 순서가 등장하면 카운트 증가
    }

    int ans = 0;

    // 등장한 상대적 순서 쌍의 개수 계산
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        int k = iter->second;
        ans += k * (k - 1) / 2; // 조합: nC2 = n * (n-1) / 2
    }

    cout << ans;
}

---

코드 설명

• 값과 인덱스 저장: - 각 차원의 데이터를 입력받고, 상대적 순서를 확인하기 위해 인덱스와 값을 pair로 저장합니다.
• 정렬 후 순서 기록: - 각 차원 데이터를 정렬한 후, 정렬된 값의 원래 인덱스를 문자열로 변환하여 저장합니다.
• map을 통한 카운트: - 동일한 상대적 순서를 가진 문자열이 등장할 때마다 map에서 카운트를 증가시킵니다.
• 중복 쌍 개수 계산: - k개의 동일한 상대 순서가 등장하면 쌍의 개수는 kC2 = k * (k - 1) / 2로 계산됩니다.

---

시간 복잡도 분석

• 정렬의 시간 복잡도는 **O(n log n)**이며, m번 반복하므로 **O(m * n log n)**입니다.
• map에 문자열을 저장하고 카운트하는 과정은 **O(n)**입니다.
• 최종적으로 시간 복잡도는 **O(m * n log n)**입니다.

---

입출력 예시

• 입력 예시:

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

• 출력 예시:

  2

---

결론

이 문제는 차원의 데이터를 정렬하여 상대적 순서를 문자열로 저장하고, 동일한 상대적 순서를 가진 차원 쌍의 개수를 map을 이용해 효율적으로 계산하는 문제입니다. 정렬과 문자열 비교를 통해 시간 복잡도를 최소화했습니다.