백준/18869번/멀티버스 II/골드5

Problem Link: https://www.acmicpc.net/problem/18869

문제 설명

Site: Baekjoon
Number: 18869
Category: Coordinate Compression
Rank: Gold 5

좌표 압축 (Coordinate Compression) 유형을 처음 마주하여 조금 난관을 겪은 문제였습니다.

좌표 압축은 주어진 배열에 저장된 값을 좌표 형태로 압축하여 문제를 해결하는 방식입니다.

예시로 10, 100, 500, 5000으로 저장된 배열이 있다면, 이를 1, 2, 3, 4로 관리하여 해결하는 방식입니다.

멀티버스 II문제는 주어진 여러 수열의 각 원소의 대소비교가 모두 동일한 경우 한 쌍의 동일한 수열이라고 판별하여 동일한 수열 쌍의 갯수를 찾아내는 문제입니다.

동일한 원소가 없는 경우에는 수열을 정렬하고 정렬된 두 수열의 인덱스 값이 모두 동일하다면 동일한 수열이라고 판별할 수 있지만, 동일한 원소가 존재하는 문제이기 때문에 이를 예외처리 해주어야 합니다.

문제 풀이

문제는 각 수열마다 정렬 후 예외처리한 과정의 결과를 string으로 만들어 이가 동일하다면 동일한 수열로 판별할 수 있게 하였습니다.

1. 각 수열의 string을 저장할 string 배열을 생성합니다.

2. 각 수열은 pair<int,int>형으로 (입력받은 원소, 인덱스) 형태로 원소를 저장합니다.

3. 수열을 오름차순으로 정렬하고, 동일한 원소는 제거하여 예외처리를 해줍니다.

   동일한 원소를 제거하지 않으면 1 1 2 6 8과 1 1 1 6 8 같은 예시가 동일한 형태가 나와 틀리게 됩니다.

4. 정렬되고 예외처리된 수열의 각 pair<int,int>원소의 second값을 string형태로 이어붙여 저장합니다.

5. 모든 수열을 비교하며 두 string이 같다면 동일한 수열로 판별하여 정답 값을 1만큼 늘립니다.

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

using namespace std;

#define PII pair<int, int>

//수열 별 string
string arr[101];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int M, N, answer = 0;
    cin >> M >> N;

    for(int i = 0; i < M; i++)
    {
      vector<PII> v(N);
	    for(int j = 0; j < N; j++)
	    {
            int num;
            cin >> num;

            v[j] = PII(num, j);
	    }

        //원소 정렬 후 동일 원소 예외처리
        sort(v.begin(), v.end(), [&](PII a, PII b) {return a.first < b.first; });
        auto it = unique(v.begin(), v.end(), [&](PII a, PII b) {return a.first == b.first; });
        v.erase(it, v.end());

        string s = "";
        for(int j = 0; j < v.size(); j++)
        {
            s += to_string(v[j].second);
        }

        //해당 수열의 string 저장
        arr[i] = s;
    }

    //동일 수열 판별
    for(int i = 0; i < M - 1; i++)
    {
	    for(int j = i+1; j < M; j++)
	    {
            if (arr[i] == arr[j])
            {
                answer++;
            }
	    }
    }

    cout << answer;

    return 0;
}