[Algorithm] 🖍️백준 2358 평행선

0. 문제

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

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

출력
첫째 줄에 답을 출력한다.

1. 아이디어

HashMap 이용
💡 x를 key, y를 value로 하는 hashmap 생성
💡 y를 key, x를 value로 하는 hashmap 생성
💡 x값이 같으면 y축에 평행, y값이 같으면 x축에 평행함
→ 같은 key값을 가진 value들이 2개 이상 존재하면, 평행한 직선 하나가 생성됨

2. 핵심 풀이

1) x를 key, y를 value로 하는 hashmap 생성

HashMap<Integer, ArrayList<Integer>> xMap = new HashMap<>();
...
ArrayList<Integer> ylist = new ArrayList<>();
...
if(xMap.containsKey(x)) {
	ylist = xMap.get(x);
}
ylist.add(y);
xMap.put(x, ylist);

2) y를 key, x를 value로 하는 hashmap 생성

HashMap<Integer, ArrayList<Integer>> yMap = new HashMap<>();
...
ArrayList<Integer> xlist = new ArrayList<>();
...
if(yMap.containsKey(y)) {
	xlist = yMap.get(y);
}
xlist.add(x);
yMap.put(y, xlist);

3) 같은 key값을 가진 value들이 2개 이상 존재하면, 평행한 직선 하나가 생성됨

int count = 0;
for(int key : xMap.keySet()) {
	if(xMap.get(key).size() >= 2)
		count++;
}
		
for(int key : yMap.keySet()) {
	if(yMap.get(key).size() >= 2)
		count++;
}

3. 코드

import java.util.HashMap;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Hash_1 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		HashMap<Integer, ArrayList<Integer>> xMap = new HashMap<>();
		HashMap<Integer, ArrayList<Integer>> yMap = new HashMap<>();
		
		for(int i=0; i<n; i++) {
			String[] s = br.readLine().split(" ");
			int x = Integer.parseInt(s[0]);
			int y = Integer.parseInt(s[1]);
			
			ArrayList<Integer> ylist = new ArrayList<>();
			ArrayList<Integer> xlist = new ArrayList<>();
			
			if(xMap.containsKey(x)) {
				ylist = xMap.get(x);
			}
			ylist.add(y);
			xMap.put(x, ylist);
			
			if(yMap.containsKey(y)) {
				xlist = yMap.get(y);
			}
			xlist.add(x);
			yMap.put(y, xlist);
		}
		
		int count = 0;
		for(int key : xMap.keySet()) {
			if(xMap.get(key).size() >= 2)
				count++;
		}
		
		for(int key : yMap.keySet()) {
			if(yMap.get(key).size() >= 2)
				count++;
		}
		
		System.out.println(count);
	}

}

4. 결과

성공✨