(C++) - 백준(BOJ) 2358 : 평행선

https://www.acmicpc.net/problem/2358

2358번: 평행선

자료구조 map을 사용하는 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

점 개수 n, 정답출력위한 변수 ans, map xMap, yMap을 선언한 뒤 입력받습니다.

📔 풀이과정

n이 10만이므로 이중 for문은 시간초과가 납니다. 따라서 nlogn시간복잡도를 가진 자료구조 map으로 해결해야합니다.

x축에 평행한 직선과 y축에 평행한 직선을 구하는 문제이므로

같은 x좌표에 대해 y좌표가 달라도 한 직선위에 있으며, 같은 y좌표에 대해 x좌표가 달라도 한 직선위에 있다는 생각에서 답을 구할 수 있습니다.

xMap은 즉, key는 x좌표이며 value는 그 x좌표를 가지고 있는 점들의 개수가 됩니다.

yMap은 key가 y좌표이며 value는 그 y좌표를 가지고 있는 점들의 개수입니다.

직선은 두 개의 점으로 이루어져 있으므로 각 map을 for loop를 수행해 2이상인 것을 세주면 답이됩니다. 세준값은 ans에 저장해줍니다.

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

map <int,int> xMap, yMap;
int n, ans;

int main(){
  cin >> n;
  for(int i = 0, x, y; i < n; i++){
    cin >> x >> y;
    xMap[x]++;
    yMap[y]++;
  }
  for(auto el : xMap){
    if(el.second >= 2) ans++;
  }
  for(auto el : yMap){
    if(el.second >= 2) ans++;
  }
  cout << ans;
}