[백준][C++] 22942. 데이터 체커

22942. 데이터 체커

22942번: 데이터 체커

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

엄청엄청엄청 고생했던 문제.

지금까지 풀어본 문제 중에 제일 어려웠던 것 같지만, 스스로 풀어내서 되게 뿌듯했다.

처음 접근은 원들을 (x + 반지름)값 오름차순으로 정렬하고 벡터에 넣어 비교하는 코드였다.

sort(vec.begin(), vec.end(), [](auto p1, auto p2) {return p1.first + p1.second > p2.first + p2.second; });

벡터는 스택처럼 사용해 닿지 않았다면 Pop_Back을 해주었다. 그런데 이때 원본 벡터를 건드리면 문제가 생길 것 같아 복사한 벡터를 스택처럼 사용해주었다.

 

겹치는 원을 발견하지 못했다면 원본 벡터에서 pop_back을 수행해주고 다시 while문을 도는 2중 while문을 구상했다.

// 가장 
while(vec.size() >= 2)
{
	vector<pair<int, int>> temp = vec;
	while(temp.size() >= 2)
	{
		if(IsTouching(temp.back(), *(temp.end() - 2));)
		{
			cout << "NO";
			return 0;
		}
		temp.erase(temp.end() - 2);
	}
}

문제는 시간이 너무 오래 걸린다는 것이었다. 거진 완전탐색이라 정확했지만, 시간이 오래 걸려 **그냥 원본 벡터를 건들면 어떨까?**라는 생각이 들었다.

 

그래서

while (vec.size() >= 2)
	{
		int result = IsTouching(vec.back(), *(vec.end() - 2));

		if (IsTouching(vec.back(), *(vec.end() - 2)))
		{
			cout << "NO";
			return false;
		}

		vec.erase(vec.end() - 2);
	}

하나의 while문으로 원본 벡터를 건드리는 도장깨기식 코드를 써보았다. 긴가민가한 마음에 제출해보니, 정답이 표시되었다.

맞은 건 기분이 좋지만, 아무리봐도 이 코드가 왜 맞는지 이해가 안 되어서 30분 동안 고민하다가, 새로운 테스트케이스를 만들어내었다.

이 테스트 케이스인데, 표시한 지점부터 오른쪽으로 비교를 하다 보면 YES가 나오게 되는데, 원래 답은 NO이다.

결국 이 테스트 케이스까지 충족한 새로운 코드는 while문을 두 번 써서 비교하는 것이었다.

이렇게 두 번 탐색. 내가 만든 테스트케이스를 충족했다.

 

전체 코드

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

bool IsTouching(pair<int, int> a, pair<int, int> b)
{
	int dist = abs(a.first - b.first);

	// 내부 동심원
	if (dist < abs(a.second - b.second) || dist == 0)
		return false;

	// 외부
	if (a.second + b.second < dist)
		return false;

	return true;
}

bool Check(vector<pair<int, int>> vec)
{
	while (vec.size() >= 2)
	{
		if (IsTouching(vec.back(), *(vec.end() - 2)))
		{
			cout << "NO";
			return false;
		}

		vec.erase(vec.end() - 2);
	}

	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int len;
	vector<pair<int, int>> vec;

	cin >> len;

	for (int i = 0; i < len; i++)
	{
		int posX, radius;
		cin >> posX >> radius;
		vec.push_back({ posX , radius });
	}

	// 중앙+반지름이 큰 순서대로 정렬 => 작은 것부터 오른쪽으로 비교
	sort(vec.begin(), vec.end(), [](auto p1, auto p2) {return p1.first + p1.second > p2.first + p2.second; });

	if (Check(vec))
	{
		// 중앙-반지름이 작은 순서대로 정렬 => 큰 것부터 왼쪽으로 비교
		sort(vec.begin(), vec.end(), [](auto p1, auto p2) {return p1.first - p1.second < p2.first - p2.second; });

		if (Check(vec))
		{
			cout << "YES";
		}
	}
}

 

맞았다고 해서 무작정 좋아할 게 아니라, 왜 맞았는지에 대해 정확히 알고 내가 쓴 코드를 정확히 이해하는 것이 중요한 것 같다.