백준 18869 멀티버스 2

문제 소개

• M개의 우주에 N개의 행성이 있다.
• 각 행성별로 크기가 주어지는데 여기서 각 우주별로 행성을 크기 순서대로 등수를 매길 것이다.
• 여기서 행성의 크기 순서가 동일한 우주는 균등한 쌍의 우주라고 하자.
• 균등한 우주의 쌍의 개수는 총 몇개일까?

문제 링크

접근 방법

• 각 우주별로 행성의 크기 순서로 등수를 매기는 과정이 가장 중요한 로직이라고 생각했다.
• 크기 순서를 알려면 우선 정렬을 해야하는데 단순히 n^2인 로직을 사용하면 안되고, nlogn인 sort 함수를 사용하기로 결정
• 각 우주별로 정렬을 하고 각 크기별로 크기 순위 몇 등인지 배열에 저장해둔다
• 이후 원본 입력 벡터를 보면서 크기 순위 몇 등인지 문자열로 저장한다.
• 문자열을 벡터로 저장해두고 모든 순위를 다 구하고 난 뒤 겹치는 문자열의 개수를 세서 출력한다.

풀이 코드

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <utility>

using namespace std;

vector< vector<int> > uni(101, vector<int>(10001));
int big[1000001];
vector<string>    couple;

int main()
{
    int    M, N, t;
    int idx = -1;
    int ret = 0;

    cin>>M>>N;
    while (M != ++idx)
    {
        for (int i = 0; i < N; i++)
        {
            cin>>uni[idx][i];
        }
    }

    for (int i = 0; i < M; i++)
    {
        string    temp;
        vector<int>    after = uni[i];

        sort(after.begin(), after.begin() + N);

        for (int j = 0; j < N; j++)
        {
            big[after[j]] = j + 1; // 이것도 그냥 map 쓰는게 빨랐을 듯(공간복잡도가 줄어들 수 있음. 최악의 케이스에는 동일)
        }

        for (int j = 0; j < N; j++)
        {
            temp += to_string(big[uni[i][j]]);
        }

        couple.push_back(temp);
    }

    // -> map에서 검사하면 더 빠르게 가능(string을 map에 저장)
    for (int i = 0; i < M - 1; i++)
    {
        for (int j = i + 1; j < M; j++)
        {
            if (couple[i] == couple[j])
                ret++;
        }
    }
    cout<<ret<<endl;
}