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

이번 강좌에서는 스위프트 언어로 코딩 테스트를 준비하기 위한 문제 하나를 해결해보겠습니다. 주제는 선분을 그룹으로 나누는 것입니다. 다음과 같은 절차를 통해 문제를 이해하고 해결 방법을 설명해보겠습니다.

문제 설명

주어진 선분들이 겹치는 경우가 있을 때, 이 선분들을 최소 몇 개의 그룹으로 나눌 수 있는지를 구하는 문제입니다. 선분은 시작과 끝의 좌표로 표현되며, 서로 겹치는 선분들은 같은 그룹으로 묶여야 합니다. 각 선분은 [start, end] 형태로 주어집니다. 예를 들면, [1, 3], [2, 5], [6, 8]과 같이 주어질 수 있습니다.

입력 형식

배열 형태로 여러 개의 선분을 입력받습니다. 예를 들어:

let segments = [[1, 3], [2, 5], [6, 8], [7, 9]]

출력 형식

선분을 나누기 위한 최소 그룹 숫자를 출력합니다. 위의 예시에서는 2가 됩니다.([1, 3]과 [2, 5]는 겹치기 때문에 같은 그룹에 속하고, [6, 8]과 [7, 9]는 다른 그룹으로 나뉩니다.)

문제 풀이

문제를 해결하기 위해 먼저 선분들을 정렬한 다음, 겹치는 선분들을 그룹으로 묶는 과정이 필요합니다. 이 문제를 해결하기 위한 전략은 다음과 같습니다:

선분들을 시작 지점으로 오름차순으로 정렬합니다.
정렬된 선분을 순회하며, 현재 그룹의 마지막 선분과 겹치는지를 확인합니다.
겹치는 경우에는 같은 그룹에 포함시키고, 그렇지 않은 경우 새로운 그룹을 만들어야 합니다.

구현

이제 위의 전략에 따라 스위프트로 코드를 작성해 보겠습니다:

func countGroups(segments: [[Int]]) -> Int {
    guard !segments.isEmpty else { return 0 }
    
    // 1. 선분 정렬
    let sortedSegments = segments.sorted { $0[0] < $1[0] }
    
    var groups = 1
    var lastEnd = sortedSegments[0][1]

    // 2. 선분 탐색
    for i in 1..

코드 설명
위 코드에서 countGroups 함수는 선분의 배열을 입력받아 최소 그룹 수를 반환합니다. 각 과정은 다음과 같습니다:

    빈 배열일 경우 그룹 수는 0을 반환합니다.
    입력된 선분을 시작 지점에 따라 정렬합니다.
    첫 번째 선분의 끝점으로 초기값을 설정합니다. 그룹 수는 1로 설정합니다.
    나머지 선분들을 순회하며, 현재 선분의 시작점이 마지막 선분의 끝점보다 작거나 같은지 확인하여 겹치는지 체크합니다.
    겹치면 마지막 선분의 끝점을 업데이트하고, 겹치지 않으면 새로운 그룹을 시작하며 그룹 수를 증가시킵니다.


시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n log n)입니다. 선분을 정렬하는 데 O(n log n)이 소요되며, 선분을 한 번 순회하여 그룹을 계산하는 데 O(n)이 추가로 소요됩니다. 따라서 최종 시간 복잡도는 O(n log n)입니다.

핵심 포인트

    선분의 겹침 여부를 정확히 확인하는 것이 중요합니다.
    정렬 후 선분을 효과적으로 처리하는 방법을 이해해야 합니다.


이번 강좌를 통하여 스위프트를 이용한 알고리즘 문제 풀이 능력을 향상시킬 수 있기를 바랍니다. 코딩 테스트를 준비하는 데 있어 위의 문제와 접근 방식은 유용하게 쓰일 것입니다. 추가적인 문제를 통해 연습하고, 다양한 알고리즘을 익히는 기회를 갖기를 권장합니다!

문제 설명

입력 형식

출력 형식

문제 풀이

구현

코드 설명

시간 복잡도 분석

핵심 포인트

관련