[99클럽 코테 스터디 TIL 12일차] 백준 2358번 평행선 해설 및 풀이 (Java)

 

백준 2358번 평행선

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

 

---

 

문제

평면에 n개의 점이 있다. 그중 두 개 이상의 점을 지나면서 x축 또는 y축에 평행한 직선이 몇 개인지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다. 좌표는 절댓값이 231보다 작은 정수이다.

출력

첫째 줄에 답을 출력한다.

 

---

문제 유형

자료 구조
정렬
해시를 사용한 집합과 맵

 

풀이 방법 도출

 

1. 주어진 점들의 x좌표, y좌표를 각각 기준으로 묶습니다.
2. x가 같은 점들은 수직선(세로선), y가 같은 점들은 수평선(가로선)을 만들 수 있습니다.
3. 각 좌표에 대해, 같은 좌표값을 가진 점이 2개 이상인 경우에만 직선을 만들 수 있습니다.
4. 같은 좌표를 가진 점들 중 2개를 선택하는 방법은 조합식: nC2 = n(n-1)/2
5. x좌표 기준으로 nC2를 더하고, y좌표 기준으로도 nC2를 더합니다.

 

 

시간 복잡도

 

• O(N)

 

 

---

처음에 작성한 코드

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  // 점의 개수

        // x, y 좌표값별로 등장 횟수를 저장할 해시맵
        Map<Integer, Integer> xMap = new HashMap<>();
        Map<Integer, Integer> yMap = new HashMap<>();

        // 입력받은 좌표를 통해 x, y값 각각 등장 횟수 세기
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            // x값 기준으로 개수 카운트
            xMap.put(x, xMap.getOrDefault(x, 0) + 1);

            // y값 기준으로 개수 카운트
            yMap.put(y, yMap.getOrDefault(y, 0) + 1);
        }

        int answer = 0;

        // x좌표가 같은 점들 중 2개를 고르는 조합 수
        for (int count : xMap.values()) {
            if (count > 1) {
                answer += count * (count - 1) / 2;
            }
        }

        // y좌표가 같은 점들 중 2개를 고르는 조합 수
        for (int count : yMap.values()) {
            if (count > 1) {
                answer += count * (count - 1) / 2;
            }
        }

        // 결과 출력
        System.out.println(answer);

        sc.close();
    }
}

 

 

처음에 count * (count - 1) / 2는 조합을 계산하는 공식으로 알고 작성했던 코드이다.

문제에서는 단순히 직선의 개수를 묻고 있으므로 직선을 한 번만 세면 충분합니다.

 

예를 들어 x=3인 좌표가 4개 있다면, 이들을 잇는 세로 직선은 단 1개입니다.

 

문제는 "두 개 이상의 점을 지나면서 평행한 직선"의 수를 묻고 있습니다.

 

x값이 같은 점이 2개 이상 있을 경우 → 세로선 1개,
y값이 같은 점이 2개 이상 있을 경우 → 가로선 1개
→ 즉, 조건 만족한 좌표값 수를 세면 됩니다.

---

 

최종 Java 코드

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<Integer, Integer> xMap = new HashMap<>();
        Map<Integer, Integer> yMap = new HashMap<>();

        // 점의 좌표 입력
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            xMap.put(x, xMap.getOrDefault(x, 0) + 1);
            yMap.put(y, yMap.getOrDefault(y, 0) + 1);
        }

        int lineCount = 0;

        // x축에 평행한 직선 개수: y좌표가 같은 점이 2개 이상이면 +1
        for (int count : xMap.values()) {
            if (count >= 2) {
                lineCount++;
            }
        }

        // y축에 평행한 직선 개수: x좌표가 같은 점이 2개 이상이면 +1
        for (int count : yMap.values()) {
            if (count >= 2) {
                lineCount++;
            }
        }

        System.out.println(lineCount);
        sc.close();
    }
}