자바 코딩테스트
2358 평행선
백엔드 개발자
2025. 4. 12. 01:33
문제
평면에 n개의 점이 있다. 그중 두 개 이상의 점을 지나면서 x축 또는 y축에 평행한 직선이 몇 개인지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다. 좌표는 절댓값이 231보다 작은 정수이다.
단순하게 구현이라면
두 좌표를 비교했을때 x좌표나 y좌표 둘중에 하나는 같아야 한다.
2차원 배열을 만들고 해당 인덱스에 1씩 더하고
1차원 순회해서 개수 구하고
2차원 순회해서 개수 구한다.
점이 n개일때 평행한 직선이 몇개인지 구하는 공식이 필요.
n개일때 중복 제거한 경우의 수
2개면 1 3개면 3 4개면 6 5 10
f(n) = f(n-1)+n-1
그러나 하기와 같이 진행시 적절한 자료구조를 생각하지 못해서 실패
package 백준.평행선_2358;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
static int countResult = 0;
static int[] memory = new int[]{0, 1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
List<List<Integer>> arr = new ArrayList<>();
for (int i = 0; i < count; i++) {
String a = br.readLine();
System.out.println(a);
Pattern aa = Pattern.compile("(\\d)\\s(\\d)");
Matcher m = aa.matcher(a);
if (m.matches()) {
int xNumber = Integer.parseInt(m.group(1));
int yNumber = Integer.parseInt(m.group(2));
arr.get(xNumber).set(yNumber,arr.get(xNumber).get(yNumber)+ 1);
}
}
for (int i = 0; i < count; i++) {
int hangCount = 0;
int yeolCount = 0;
for (int j = 0; j < count; j++) {
hangCount += arr.get(i).get(j);
yeolCount += arr.get(j).get(i);
}
countResult += (getWayCount(hangCount) + getWayCount(yeolCount));
}
System.out.println(countResult);
br.close();
}
private static int getWayCount(int hangCount) {
if (hangCount == 0) return 0;
if (hangCount == 1) return 0;
if (hangCount == 2) return 1;
if (memory[hangCount] != 0) {
return memory[hangCount];
} else {
int a = getWayCount(hangCount-1) + 1;
memory[hangCount] = a;
return a;
}
}
}
자료구조를 이용하는 방법
map 2개를 이용해서 x좌표, y좌표별로 같은 경우 개수를 센다.
x, y 좌표 각각 같은 것들이 2개이상이면 선1개라고 볼 수 있기 때문에.
점이 한 선에 여러개 있으면 1개로 취급되고,
같은 좌표일 경우에는 2개로 된다고 한다.
package 백준.평행선_2358;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
Map<Integer, Integer> xMap = new HashMap<Integer, Integer>();
Map<Integer, Integer> yMap = new HashMap<Integer, Integer>();
//x,y를 map으로 따로 두는 아이디어
for (int i = 0; i < count; i++) {
String a = br.readLine();
System.out.println(a);
int [] aa = Arrays.stream(a.split(" ")).mapToInt(Integer::parseInt).toArray();
int xNumber = aa[0];
int yNumber = aa[1];
System.out.println("xNumber : "+xNumber);
System.out.println("yNumber:"+yNumber);
if (xMap.containsKey(xNumber)) {
xMap.put(xNumber, xMap.get(xNumber) + 1);
} else {
xMap.put(xNumber, 1);
}
if (yMap.containsKey(yNumber)) {
yMap.put(yNumber, yMap.get(yNumber) + 1);
} else {
yMap.put(yNumber, 1);
}
}
int result = 0;
for (Map.Entry<Integer, Integer> entry : xMap.entrySet()) {
if (entry.getValue() >= 2) {
result++;
}
}
for (Map.Entry<Integer, Integer> entry : yMap.entrySet()) {
if (entry.getValue() >= 2) {
result++;
}
}
System.out.println(result);
br.close();
}
}