[작심큰일] 250812 - 백준 2358번: 평행선

📜 백준 2358번: 평행선 (https://www.acmicpc.net/problem/2358)

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

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        Map<Integer, Integer> xCount = new HashMap<>();
        Map<Integer, Integer> yCount = new HashMap<>();
        Set<String> pointSet = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            String[] inputs = input.split(" ");
            int x = Integer.parseInt(inputs[0]);
            int y = Integer.parseInt(inputs[1]);
            
            xCount.put(x, xCount.getOrDefault(x, 0) + 1);
            yCount.put(y, yCount.getOrDefault(y, 0) + 1);
        }
        
        long result = 0;
        
        for (int i : xCount.values()) {
            if (i >= 2) {
                result++;
            }
        }
        for (int i : yCount.values()) {
            if (i >= 2) {
                result++;
            }
        }
        
        System.out.println(result);
    }
}

 

이문제는 각 모든 점들의 x값, y값들이 몇개인지 Map으로 저장하고 이후 각 값들이 2개 이상이라면 직선이 생길 수 있다고 생각하고 값을 하나씩 더하는 로직이다.

 

 

 

🪛 피드백

📝 코드 설명

- xCount, yCound HashMap 으로 각각 x 축, y 축 평행 여부 판단

- 좌표의 개수가 2개 이상 일때만 직선 으로 간주

📊 복잡도 분석

시간 복잡도: O(N)

공간 복잡도: O(N)

⚡ 최적화 팁

1. [HashMap vs TreeMap] : 만약 정렬이 필요했다면 TreeMap 을 사용했을 것. 하지만 정렬이 필요 없는 문제였기 때문에 HashMap 사용

2. [중복 허용 ] : 문제에서 중복을 허용하기 때문에, Set 이 아닌 Map 을 사용

🎯 학습 포인트

2 차원 좌표를 HashMap 으로 분류 하는 방식

🔗 관련 문제

- HashMap, TreeMap, Set, Map 등에 대해 어떤 것이 적절할 지 항상 고민

- 입력제한이 클 경우 시간 공간 복잡도 고려!