백준 5588: 별자리 찾기

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

 

약 10분 간 고민을 했고, 별자리 위치와 사진 속 별의 위치의 차이를 구한뒤에, unordered_map에 이 차이를 count하고, 이 count가 별자리 별 갯수와 동일하다면, 그것이 정답일것이다란 결론을 내렸다. 그렇게 구성한 코드는

 

#include <iostream>
#include <unordered_map>

using namespace std;

int N, M, sx[1001], sy[1001], px[201], py[201];
struct pairHash {
public:
	size_t operator()(const pair<int, int>& p) const
	{
		return hash<int>()(p.first) & hash<int>()(p.second);
	}
};
unordered_map<pair<int, int>, int, pairHash> um;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M;
	for (int i = 0; i < M; i++) cin >> sx[i] >> sy[i];
	cin >> N;
	for (int i = 0; i < N; i++) cin >> px[i] >> py[i];
	for(int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			++um[{sx[i] - px[j], sy[i] - py[j]}];
	for(const pair<pair<int, int>, int> &p : um)
		if (p.second == M)
		{
			cout << -p.first.first << " " << -p.first.second << '\n';
			break;
		}
}

다음과 같다. 그런데, 이 코드는 제출하자마자 틀렸다는 표시를 하였다.

이후로 hash 함수를 여러번 수정하거나, 중복된 위치가 주어질 경우도 고려하기도 했다. 결국 어느쪽도 틀린 나는, 구글링을 거쳐서 코드를 수정하였다.

https://hichoe95.tistory.com/69

백준 5588문제

이 코드는 별자리의 별 위치 중 하나는 반드시 매칭 되어야하기 때문에 별자리의 별 하나를 기준 그것(여기선 인덱싱 0인 별 위치)을 두어서, 사진 속 별 위치의 차이점을 구한 뒤에, 이 차이점과 별자리 별 위치의 합이 사진의 별 위치가 있는지 확인하고, 전부 있으면 그것이 정답이다.

#include <iostream>
#include <set>

using namespace std;

int N, M, sx[1001], sy[1001], px[201], py[201];

set<pair<int, int>> um, pm;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M;
	for (int i = 0; i < M; i++) cin >> sx[i] >> sy[i];
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> px[i] >> py[i];
		pm.insert({px[i], py[i]});
	}
	for (int idx = 0; idx < N; idx++)
	{
		bool f = true;
		int x = px[idx] - sx[0]; int y = py[idx] - sy[0];
		for (int i = 0; i < M; i++)
		{
			if (pm.find({ sx[i] + x, sy[i] + y }) == pm.end())
			{
				f = false;
				break;
			}
		}
		if (f)
		{
			cout << x << " " << y << '\n';
			break;
		}
	}
}

그런데 이것도 틀렸다. 분명 블로그의 코드와 큰 차이가 없는 것 같은데, 왜 틀렸는지 이해가 안되었다.

다시 코드를 천천히 살펴본 결과 너무 기본적인 실수를 한 것을 깨달았다. 배열 크기를 잘못잡았다. 별자리 위치와 사진의 별 위치 배열 크기가 반대가 되었다. 이러면 OutOfBound 에러가 발생할 줄 알았는데, 그냥 틀려서 한참 헤메었다.

#include <iostream>
#include <unordered_map>

using namespace std;

int N, M, sx[1001], sy[1001], px[1001], py[1001];
struct pairHash {
public:
	size_t operator()(const pair<int, int>& p) const
	{
		return hash<int>()(p.first) & hash<int>()(p.second);
	}
};
unordered_map<pair<int, int>, int, pairHash> um;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M;
	for (int i = 0; i < M; i++) cin >> sx[i] >> sy[i];
	cin >> N;
	for (int i = 0; i < N; i++) cin >> px[i] >> py[i];
	for(int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			++um[{sx[i] - px[j], sy[i] - py[j]}];
	for(const pair<pair<int, int>, int> &p : um)
		if (p.second == M)
		{
			cout << -p.first.first << " " << -p.first.second << '\n';
			break;
		}
}

#include <iostream>
#include <set>

using namespace std;

int N, M, sx[1001], sy[1001], px[1001], py[1001];

set<pair<int, int>> um, pm;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M;
	for (int i = 0; i < M; i++) cin >> sx[i] >> sy[i];
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> px[i] >> py[i];
		pm.insert({px[i], py[i]});
	}
	for (int idx = 0; idx < N; idx++)
	{
		bool f = true;
		int x = px[idx] - sx[0]; int y = py[idx] - sy[0];
		for (int i = 0; i < M; i++)
		{
			if (pm.find({ sx[i] + x, sy[i] + y }) == pm.end())
			{
				f = false;
				break;
			}
		}
		if (f)
		{
			cout << x << " " << y << '\n';
			break;
		}
	}
}

정답률 70%의 문제를 단순한 실수로 이렇게 틀린 사람은 별로 없을것 같다..