백준 20529번 가장 가까운 세 사람의 심리적 거리 C++ (실버1)

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

 

n이 10만까지 들어올 수 있기 때문에 하나씩 다 둘러보면 시간초과가 나기때문에 다른 방법을 생각해야 한다.

MBTI는 종류가 한정되어있기때문에 입력받은 MBTI중 2개씩 짝을 짓고 n만큼 순회하면

최대 16 * 16 * 100000으로 모든 경우를 순회할 수 있다.

물론 입력받은 MBTI가 1개인데 셋다 같은 MBTI일수는 없기때문에 그런 부분에 대해서는 예외처리를 해주었다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int GetDist(string a, string b)
{
    int ret = 0;
    for (int i = 0; i < 4; i++)
    {
        if (a[i] != b[i]) ret++;
    }
    return ret;
}

int GetDist(string a, string b, string c)
{
    int ret = 0;
    ret += GetDist(a, b);
    ret += GetDist(b, c);
    ret += GetDist(a, c);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    int n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        vector<string> v(n);
        map<string, int> m;
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            m[v[i]]++;
        }
        vector<pair<string, int>> v2;
        for (auto it : m)
        {
            v2.push_back({ it.first, it.second });
        }
        int ans = INT_MAX;
        for (auto it = m.begin(); it != m.end(); ++it)
        {
            for (auto it2 = it; it2 != m.end(); ++it2)
            {
                for (int i = 0; i < n; i++)
                {
                    if ((v[i] == it->first) && (v[i] == it2->first)) {
                        if (m[v[i]] < 3) continue;
                    }
                    else if (v[i] == it->first || v[i] == it2->first || it->first == it2->first)
                    {
                        if (m[v[i]] < 2) continue;
                    }
                    ans = min(ans, GetDist(v[i], it->first, it2->first));
                }
            }
        }
        cout << ans << "\n";
    }
}

 

제출해서 통과하기는 했는데 다른 사람의 코드들의 시간이 굉장히 짧아서 다른 방법이 있나 하고 찾아봤더니 비둘기집 원리라는 방법으로 해결한 사람이 많았다.

mbti는 16개가 최대여서 n이 32보다 크면 무조건 3개는 중복이기 때문에 n이 32이하일때만 전체 순회를 하면 쉽게 해결할 수 있다.