자바 코딩테스트 강좌, 선분을 그룹으로 나누기

안녕하세요! 이번 코딩테스트 강좌에서는 주어진 선분을 그룹으로 나누는 문제를 다룹니다. 이 문제는 여러 프로그래밍 언어에서 자주 출제되는 문제 중 하나이며, 특히 선분의 겹침 여부를 판단하고, 이를 통해 효율적으로 그룹화하는 능력을 요구합니다.

문제 설명

주어진 선분의 리스트가 있을 때, 이 선분들을 겹치는 부분이 있을 경우 같은 그룹으로 묶어야 합니다. 선분은 두 좌표 (x1, x2)로 표현되며, x1은 항상 x2보다 작습니다. 즉, 각 선분은 [x1, x2]의 형태로 주어집니다.

문제 정의

함수를 정의하세요:

public int groupLineSegments(int[][] segments)

입력

• 선분의 수: n (1 ≤ n ≤ 100,000)
• segments: 선분을 나타내는 2차원 배열 (각 선분의 시작과 끝 점)

출력

• 서로 겹치는 선분 그룹의 수

예시

문제 해결 과정

이 문제를 해결하기 위해서는 선분의 겹침을 판단하고, 이를 기반으로 그룹을 형성하는 것이 필요합니다. 우리는 다음과 같은 알고리즘을 사용할 수 있습니다.

알고리즘 단계

• 1. 선분을 시작점 기준으로 정렬합니다.
• 2. 시작과 끝 점을 확인하며 그룹을 나눕니다.
• 3. 각 그룹의 끝 점이 다음 그룹의 시작 점보다 크거나 같으면 같은 그룹으로 묶습니다.

구현

자바로 이 알고리즘을 구현해 보겠습니다.

import java.util.Arrays;

public class LineSegmentGrouping {
    
    public int groupLineSegments(int[][] segments) {
        // 선분을 시작점 기준으로 정렬
        Arrays.sort(segments, (a, b) -> Integer.compare(a[0], b[0]));
        int groupCount = 0;
        int currentEnd = Integer.MIN_VALUE;

        for (int[] segment : segments) {
            if (segment[0] > currentEnd) {
                // 새로운 그룹 시작
                groupCount++;
                currentEnd = segment[1];
            } else {
                // 그룹의 끝 점 업데이트
                currentEnd = Math.max(currentEnd, segment[1]);
            }
        }

        return groupCount;
    }
    
    public static void main(String[] args) {
        LineSegmentGrouping lsg = new LineSegmentGrouping();
        int[][] segments = {{1, 3}, {2, 4}, {5, 6}, {8, 10}, {9, 12}};
        System.out.println("그룹 수: " + lsg.groupLineSegments(segments)); // 3
    }
}

코드 설명

위 코드는 선분을 그룹으로 나누기 위한 간단하지만 효율적인 방법을 보여줍니다.

• 정렬: 첫 번째 줄에서 Arrays.sort를 이용하여 선분을 시작점 기준으로 오름차순 정렬합니다. 이는 겹치는 선분을 쉽게 판단할 수 있게 합니다.
• 그룹 카운트: groupCount 변수를 통해 그룹 수를 카운트하며, currentEnd를 이용해 현재 그룹의 최대 끝 점을 기억합니다.
• 조건 판단: 각 선분을 체크하며 새로운 그룹을 시작할지, 현재 그룹의 끝 점을 업데이트할지 판단합니다.

시간 복잡도

이 솔루션의 시간 복잡도는 O(n log n)입니다. 선분을 정렬하는 데 O(n log n) 시간이 소요되고, 그룹화를 위한 반복문은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.

결론

선분을 그룹으로 나누는 문제는 겹치는 구간을 판단하는 능력을 요구하며, 다양한 응용이 가능합니다. 이번 강좌를 통해 알고리즘 문제를 해결하는 방법과 자바 코딩 능력을 향상시킬 수 있기를 바랍니다.