📌문제접근
문제 : 백준 2358 (https://www.acmicpc.net/problem/2358)
유형 : 정렬, 해시테이블
평면에 n개의 점이 있다. 그중 두 개 이상의 점을 지나면서 x축 또는 y축에 평행한 직선이 몇 개인지 알아내는 프로그램을 작성하시오.
입력 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다. 좌표는 절댓값이 231보다 작은 정수이다.
1) x축 또는 y축에 평행하려면 y좌표가 동일한 두 점이거나 x좌표가 동일한 두점이면 된다.
2) n이 (1 ≤ n ≤ 100,000) 이므로 시간복잡도에 신경을 써보자.
📌제출코드
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int n, x, y;
unordered_map<int, int> xCount, yCount;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
xCount[x]++;
yCount[y]++;
}
int result = 0;
for (auto& p : xCount) {
if (p.second > 1) result++;
}
for (auto& p : yCount) {
if (p.second > 1) result++;
}
cout << result << endl;
return 0;
}📌문제 해결
문제의 기본적인 해결 방법은 동일한 x, y좌표가 몇번 들어오는지 카운트 하여 2번 이상인 경우 하나의 평행선을 만들 수 있다. => 좌표값을 key로 하는 해시맵에 등장 횟수를 카운트 하여 저장한다.
-
'같은 좌표는 서로 다른 점으로 간주한다' 의 해석
가장 많은 시간을 고민하게 했던 부분이다.
우선 나의 해석은 (1) 같은 좌표는 서로 다른 점으로 카운트 한다. (2) 서로 다른 두 점으로 평행선을 만들 수 있다. (3) 그러므로 x좌표와 y좌표의 개수를 카운트 할때 해당 key값에 완전히 동일한 좌표의 점만 들어온 경우에는 평행선을 만들 수 없고, 다른 점이 있어야 평행선을 만들 수 있다.
위의 내용을 표현하기 위해서 count를 저장하는 맵뿐 아니라 해당 좌표의 점이 중복되는 점인지 다른 점인지를 확인하는 추가적인 자료구조(적절한 자료구조를 생각하지 못함)이 필요했다. 몇 시간을 고민하는데 원하는 구현이 어려워 문제를 구글링했더니
입력이 같은 두 점으로도 직선을 만들 수 있다는 것을 알게되었다.
그럼 (2)에 대한 고려없이 (1)만 고려하여 카운트를 하면 되기에 구현을 빠르게 마쳤다. 문제 해석의 애매함으로 고민을 많이 했지만 여러가지 구현 방법을 고민했던 시간이 의미있었다.. -
시간복잡도
해시맵을 이용하여 탐색과 삽입에 평균 O(1)의 시간복잡도가 되도록 구현하였다. 최종 코드의 시간복잡도는 평균 O(n)이다.
📌오늘의 회고
원하는 구현을 위해 자료구조 공부가 더 필요함을 느꼈다.
