[C++] 백준 2358번:평행선 (map)

문제링크

2358번: 평행선

문제

평면상에 n개의 점이 있다. 이 점들 중에 서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

출력

첫째 줄에 답을 출력한다.

 

풀이

문제가 애매하게 설명이 되어있다. "만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다." 이 부분이 잘 이해가 가지 않았는데 질문에 가서 보니 다른 사람들도 문제가 애매한 것 같다는 이야기가 많았다.

우선 문제를 제대로 이해해보도록 하자.

 

만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 라는 의미는

x, y의 값이 같은 두 점이 들어와도 두 점을 다른 점으로 보고 직선을 만들 수 있다는 의미이다. 그리고 이때의 직선은 x에 평행한 직선과 y에 평행한 직선 총 2개가 된다.

예를 들어 (0,2), (0,2) (3,3)이 입력으로 들어왔다고 하면 세 점으로 만들 수 있는 직선은 x=0, y=2가 되므로 총 2개가 된다.

다른 예를 들어보면 (0,2), (0,2), (0,10)이 입력으로 들어왔다고 하면 (0,2), (0,2) 두 점을 이용해서 만들 수 있는 직선은 x=0, y=2이다. 그리고 (0,2), (0,10) 두 점을 이용하여 만들 수 있는 직선은 x=0 이다. 하지만 이미 앞에서 x=0을 구했기 때문에 이는 세어주지 않고 답이 2개가 되는 것이다.

 

x, y축에 평행한 직선을 세는 것이 중요 포인트이다. x축과 y축에 평행하기 위해서는 두 점의 x좌표가 같거나 y좌표가 같아야 한다. 그리고 같은 점이 또 나오더라도 이미 그 직선은 세어주었기 때문에 무시해도 된다.

1. x의 좌표가 나온 횟수를 저장할 map, y의 좌표가 나온 횟수를 저장할 map 두 개를 만들어준다.
2. 입력을 받고 각 좌표에 따라 횟수를 count해준다.
3. 2번 이상 나온 횟수 x,y의 좌표를 세어주면 된다.

 

코드

#include <iostream>
#include <map>
using namespace std;
 
int n, cnt;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    map<int, int> X, Y;
 
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
 
        X[x]++;    // x좌표 나온 횟수 증가
        Y[y]++;    // y좌표 나온 횟수 
    }
 
    for (auto iter = X.begin(); iter != X.end();iter++) {
        if (iter->second >= 2) {
            cnt++;
        }
    }
 
    for (auto iter = Y.begin(); iter != Y.end(); iter++) {
        if (iter->second >= 2) {
            cnt++;
        }
    }
    cout << cnt;
}