이 문제에서는 두 개의 배열 x[]와 y[]가 주어지며, 각 쌍 (x, y)는 2차원 평면 위의 한 점의 좌표를 나타냅니다. 우리의 과제는 모든 좌표점을 오름차순으로 출력하고, 각 점이 나타난 횟수(빈도)를 함께 출력하는 것입니다.
문제 이해를 위한 예시
입력: x[] = {0, 1, 1, 0, 0} ; y[] = {1, 2, 2, 2, 1}
출력:
(0, 1) = 2
(1, 2) = 2
(0, 2) = 1해결 방법
이 문제를 해결하려면 각 좌표점의 등장 빈도를 저장해야 합니다. 이를 위해 맵(map) 자료구조를 활용하는 것이 가장 효과적입니다.
- 맵의 키(key): 좌표점을 나타내는 쌍 (x[i], y[i])
- 맵의 값(value): 해당 점이 등장한 횟수(정수형 빈도)
std::map은 내부적으로 키를 기준으로 자동 정렬되기 때문에, 별도의 정렬 작업 없이도 좌표점들이 오름차순으로 출력됩니다. pair<int, int> 타입은 기본적으로 first 요소를 먼저 비교하고, 값이 같으면 second 요소를 비교하므로 좌표점이 자연스럽게 사전식 순서(lexicographic order)로 정렬됩니다.
다음 프로그램은 위 해결 방법의 실제 구현 예시입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void printFrequencyofPoint(int x[], int y[], int n){
map<pair<int, int>, int> pFreq;
for (int i = 0; i < n; i++)
pFreq[make_pair(x[i], y[i])]++;
map<pair<int, int>, int>::iterator i;
for (i = pFreq.begin(); i != pFreq.end(); i++) {
cout<<"("<<(i->first).first << ", "<< (i->first).second << ") -> ";
cout<<i->second << "\n";
}
}
int main() {
int x[]={0, 1, 1, 0, 0};
int y[]={1, 2, 2, 2, 1};
int n=5;
cout<<"각 점과 그 등장 빈도는 다음과 같습니다 :\n";
printFrequencyofPoint(x, y, n);
return 0;
}
실행 결과
각 점과 그 등장 빈도는 다음과 같습니다 :
(0, 1) -> 2
(0, 2) -> 1
(1, 2) -> 2
코드 설명
- 먼저 map<pair<int, int>, int> 타입의 맵 pFreq를 선언하여 각 좌표점의 빈도를 저장합니다.
- 배열을 순회하면서 make_pair(x[i], y[i])로 좌표점을 만들고, 해당 키의 값을 증가시킵니다(++)
- 모든 입력 처리가 끝나면 반복자(iterator)를 사용해 맵을 처음부터 끝까지 순회하며 각 좌표점과 빈도를 출력합니다.
시간 복잡도
맵에 데이터를 삽입하고 조회하는 연산은 O(log N)의 시간이 소요되므로, 전체 알고리즘의 시간 복잡도는 O(N log N)입니다. 여기서 N은 입력 점의 개수입니다. 만약 정렬된 출력이 필요 없다면 unordered_map을 사용하여 O(N)으로 최적화할 수 있습니다.