가장 가까운 세 사람의 심리적 거리 [C++]

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

난이도: ⚪

1. 문제 설명

2. 문제 접근

• 비둘기 집 원리
  • n개 보다 많은 물건을 n개의 집합에 나누어 넣는다면 적어도 어느 한 집합에는 2개 이상의 물건이 속하게 된다는 내용이 비둘기집의 원리이다.
  • mbti는 총 16개다. 즉 32(16 * 2)개 를 넘기면 같은 mbti를 가진 학생이 3명이 된다는 말이다.
    • 그렇다면 이 학생들의 거리는 0이라고 볼 수 있다.

1. N의 범위는 3 < 100,000이지만 비둘기집의 원리를 이용하여 N이 32개가 넘는 케이스의 값을 0으로 만들 수 있다.
2. 3중 반복문을 이용해 3개의 mbti를 선택하여 거리를 확인하고 최소 거리를 갱시신시킨다.
   
   

3. 제출 코드

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

using namespace std;
int main(void)
{
	int T, N;
	cin >> T;

	// 테스트 케이스 만큼 반복.
	for (int t = 0; t < T; t++)
	{
		// mbti를 입력받을 벡터.
		vector<string> mbti;
		cin >> N;

		// mbti 입력.
		for (int i = 0; i < N; i++)
		{
			string temp;
			cin >> temp;

			mbti.push_back(temp);
		}

		// 비둘기집 원리를 이용하여 N이 32개를 초과한다면 0을 출력하고 다음 테스트 케이스를 실행한다.
		if (N > 32)
		{
			cout << 0 << '\n';
			continue;
		}
		
		// 최대 거리는 8이다.
		int distance = 8;

		// mbti벡터의 원소들을 비교하여 거리가 가장 작은 값으로 distance를 초기화한다.
		for (int i = 0; i < mbti.size() - 2; i++)
		{
			string temp1 = mbti[i];
			for (int j = i + 1; j < mbti.size() - 1; j++)
			{
				string temp2 = mbti[j];
				for (int k = j + 1; k < mbti.size(); k++)
				{
					string temp3 = mbti[k];
					for (int l = 0; l < 4; l++)
					{
						int dis1 = 0;
						int dis2 = 0;
						int dis3 = 0;

						for (int k = 0; k < 4; k++)
						{
							if (temp1[k] != temp2[k])
								dis1++;
							if (temp1[k] != temp3[k])
								dis2++;
							if (temp2[k] != temp3[k])
								dis3++;
						}
						distance = min(distance, dis1 + dis2 + dis3);
					}
				}
			}
		}
		cout << distance << '\n';
	}
	return 0;
}

4. 최적화

기존의 코드는 220ms가 걸렸다.

// distance를 저장할 벡터
vector<int> dis;
for (int i = 0; i < v.size() - 2; i++)
{
	string temp1 = v[i];
	for (int j = i + 1; j < v.size() - 1; j++)
	{
		string temp2 = v[j];
		for (int k = j + 1; k < v.size(); k++)
		{
			string temp3 = v[k];
			for (int l = 0; l < 4; l++)
			{
				int dis1 = 0;
				int dis2 = 0;
				int dis3 = 0;

				for (int k = 0; k < 4; k++)
				{
					if (temp1[k] != temp2[k])
						dis1++;
					if (temp1[k] != temp3[k])
						dis2++;
					if (temp2[k] != temp3[k])
						dis3++;
				}
                // 세 사람의 심리적 거리를 벡터에 추가한다.
				dis.push_back(dis1 + dis2 + dis3);
			}
		}
	}
    // 벡터를 정렬하여 최단 거리를 뽑아온다.
	sort(dis.begin(), dis.end());
	cnt = dis[0];
}

최종 제출 코드는 12ms까지 단축했는데 이전 코드가 오래 걸린 이유는 모든 거리를 벡터에 입력하고 그 거리를 sort하는데 시간이 오래 걸린것 같다.

그래서 반복할 때 마다 최소 거리를 구하는 방법으로 변경하고 sort하는 시간이 사라지니 시간을 줄일 수 있었다.

5. 결과