[ 백준 - 2358 ] 평행선

이번 문제는 고민 했던 것보다 꽤 쉽게 풀어져 가져와보았습니다.

 

위와 같이 문제가 주어졌습니다.

 

쉽게 생각해보면 점이 n개 주워졌을 때 x나 y에 평행이 되는 선의 갯수를 구하라는 뜻인데,

여기서 살짝 생각해보면 좋은 점은 x와 y에 평행이 되려면 어떤 조건을 가져야하는가 입니다.

 

x에 평행이 되려면 두 점의 y좌표는 동일해야할 것이고, y에 평행이 되려면 x좌표가 동일해야할 것 입니다.

 

즉, x점을 기준으로 묶은 자료와 y점을 기준으로 묶은 자료만 있다면 쉽게 문제를 풀 수 있는 것입니다.

public class Main {

    static Map<Integer, Integer> xLineMap = new HashMap<>();
    static Map<Integer, Integer> yLineMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            String[] strs = br.readLine().split(" ");
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
            xLineMap.put(x, xLineMap.getOrDefault(x, 0) + 1);
            yLineMap.put(y, yLineMap.getOrDefault(y, 0) + 1);
        }
        int answer = 0;
        for (int count : xLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        for (int count : yLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

 

 

위 문제를 확인해보면 2초의 시간초가 주어지고, n은 최대 100,000이라고 합니다.

이를 통해보면 알고리즘은 O(n)의 성능을 가지고 있도록 작성하는 것이 합리적이라 생각합니다.

 

위 알고리즘을 보면 n을 받아 n번 반복함으로 O(n)의 시간복잡도를 가지고 있다고 볼 수 있습니다.

또한, n을 받아 사용하는 데이터들을 보면 n개의 데이터들만을 활용하는 것을 볼 수 있어 공간복잡도 또한 O(n) 혹은 O(2n)의 복잡도를 가지고 있습니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)