[Swift 알고리즘] NumberOfDiscIntersections - Codility

NumberOfDiscIntersections coding task - Learn to Code - Codility

---

문제 분석

겹치는 원의 개수를 구한다
 겹치기만 하면 되니까, x축만 고려하자
 겹친다의 정의: i번째 원의 max 값 >= i+1번째 원의 min 값
 O(N^2)하면 쉽게 풀리지만, N = 100,000이므로 불가능

구글링

 시작점과 끝점의 배열을 각각 구한다
 각각 오름차순으로 정렬한다
 시작점 배열을 기준으로 탐색하며, 활성화된 원의 개수를 하나씩 추가한다
     다음 순서 원을 탐색할 때,
     현재 원의 시작점 < 이전까지 가장 큰 원의 끝점인지 확인한다.
         아니라면 조건을 성립할 때까지 탐색하며 활성화된 원을 제거한다.
     기존 활성화된 원의 개수를 정답에 더한다.
     정답이 조건을 넘어서면 -1을 반환한다.

참고한 풀이

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count
    var starts = [Int]()
    var ends = [Int]()

    for i in 0..<size {
        starts.append(i - A[i])
        ends.append(i + A[i])
    }

    starts.sort()
    ends.sort()

    var intersections = 0
    var activeDiscs = 0
    var endIdx = 0

    for start in starts {
        while endIdx < size && ends[endIdx] < start { // 겹치지 않는 상황
            activeDiscs -= 1
            endIdx += 1
        }
        intersections += activeDiscs // 지금까지 활성화된 디스크 수를 더하고
        activeDiscs += 1 // 디스크 수 + 1

        if intersections > 10_000_000 {
            return -1
        }
    }

    return intersections
}

회고

꽤 어려웠다. 코딜리티 문제는 난도가 들쭉날쭉하다.

시작점과 끝점 만을 고려한다는 것에는 접근을 했다.

그러나 정렬을 해도 된다는 생각을 하지 못 했다.

순서쌍을 구하는 것이 아니라, 카운트만 하면 되니까 정렬을 해서 따져도 문제가 없다.

점화식 만드는 훈련을 지속하자.

 

참고

https://study-ihl.tistory.com/175