2D 평면 위에 n개의 점이 주어졌을 때, 이 점들을 좌우 대칭으로 반사시키는 y축에 평행한 직선이 존재하는지 확인하는 문제입니다. 즉, 모든 점을 어떤 직선을 기준으로 반사했을 때, 반사된 점들의 집합이 원래 점들의 집합과 완전히 같아지는 선이 있는지 판별해야 합니다.
예를 들어 입력이 points = [[1,1],[-1,1]]과 같다면,
두 점은 x = 0을 기준으로 서로 대칭이므로 출력은 true가 됩니다.
문제 해결 접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다. 만약 대칭축이 존재한다면, 그 축은 반드시 x좌표의 최솟값과 최댓값의 정중앙에 위치해야 합니다. 따라서 각 점을 이 가상의 축을 기준으로 반사했을 때, 반사된 점도 반드시 존재해야 합니다.
알고리즘 단계
- 점들을 저장할 하나의 집합(set)
ok를 정의합니다. n:= 점의 개수minVal:= 양의 무한대(INT_MAX)maxVal:= 음의 무한대(INT_MIN)- i가 0부터 n-1까지 반복하며:
minVal:= minVal과 points[i][0] 중 작은 값maxVal:= maxVal과 points[i][0] 중 큰 값- points[i]를 집합
ok에 삽입 mid:= maxVal + minVal (대칭축 x좌표의 2배 값)- 모든 점에 대해 다시 반복하며:
x:= points[i][0],y:= points[i][1]x:= mid − x (반사된 x좌표 계산)- {x, y}가 집합
ok에 없으면 false 반환 - 모든 점이 통과하면 true 반환
동작 원리 이해하기
mid = maxVal + minVal을 사용하는 이유는 다음과 같습니다. 대칭축의 x좌표를 c라고 하면, 한 점 x의 반사점은 2c − x입니다. 여기서 2c가 바로 maxVal + minVal이 되므로, 굳이 나눗셈 없이 정수 연산만으로 반사 좌표를 깔끔하게 구할 수 있습니다. 또한 집합을 사용하면 각 점의 존재 여부를 O(log n) 시간에 빠르게 확인할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isReflected(vector<vector<int>>& points) {
set<vector<int>> ok;
int n = points.size();
int minVal = INT_MAX;
int maxVal = INT_MIN;
for (int i = 0; i < n; i++) {
minVal = min(minVal, points[i][0]);
maxVal = max(maxVal, points[i][0]);
ok.insert(points[i]);
}
int mid = maxVal + minVal;
for (int i = 0; i < n; i++) {
int x = points[i][0];
int y = points[i][1];
x = mid - x;
if (!ok.count({ x, y }))
return false;
}
return true;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,1},{-1,1}};
cout << (ob.isReflected(v));
}입력
{{1,1},{-1,1}}출력
1
복잡도 분석
이 알고리즘의 시간 복잡도는 점을 두 번 순회하고 집합 조회를 수행하므로 O(n log n)이며, 공간 복잡도는 모든 점을 저장해야 하므로 O(n)입니다. 중복된 점이 있더라도 set이 자동으로 처리해주기 때문에 안정적으로 동작한다는 장점이 있습니다.