백준 13423 Three dots

출처: www.acmicpc.net/problem/13423

분류: 이분 탐색

---

접근방식

간격이 같은 점 3개가 몇 개나 있는지 찾는 문제입니다.

이 문제는 이분탐색을 사용한 n^2 * logN 과 n^2 의 두 가지 풀이가 가능합니다.

두 풀이 모두 기본적으로 주어진 점들은 정렬을 하고 시작합니다.

 

먼저 이분 탐색을 어떻게 사용하는지 살펴보겠습니다.

원리는 간단합니다! 점 2개를 선택하고 마지막 점이 있는지 없는지를 이분탐색으로 찾아줍니다. 

점 2개를 선택해서 거리가 나왔다면 두 번째 점 + 거리 에 해당하는 점이 있는지 찾아주면 됩니다.

저는 이분탐색의 범위를 그냥 매번 0과 n-1 로 두고 시작했는데 두 번째 점까지는 선택하고 왔기 때문에 low의 범위는 좁혀주면 좀 더 효율적일 것 같아요!

for i in 0..<n {
    for m in i+1..<n {
        let distance = dots[m] - dots[i]
        if search(dots[m] + distance) != nil {
            sameDots += 1
        }
    }
}

 

다른 풀이는 투 포인터의 접근법으로 볼 수 있을 것 같네요 🤔
중간 점을 먼저 정하고
양 끝에서부터 같은 간격의 점이 있는지 확인하는 방법입니다.
(중간 점과 왼쪽 점 사이의 거리) 와 (중간 점과 오른쪽 점 사이의 거리) 를 비교합니다.

중간 점과 왼쪽 점 사이의 거리가  더 크다면 왼쪽을 +1 만큼 옮겨주고 반대라면 오른쪽 점을 -1만큼 옮겨줍니다.

이렇게 하면  n^2으로 확인할 수 있습니다.

for i in 0..<n {
    var low = 0
    var high = n-1
    
    while low < high {
        let lowDist = dots[i] - dots[low]
        let highDist = dots[high] - dots[i]
        
        if lowDist == highDist {
            sameDots += 1
            low += 1
        } else if lowDist > highDist {
            low += 1
        } else {
            high -= 1
        }
    }
}

 

해결방법

이분탐색

for _ in 0..<Int(readLine()!)! {
    let n = Int(readLine()!)!
    let dots = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: <)
    
    func search(_ num: Int) -> Int? {
        var low = 0
        var high = n-1
        while low <= high {
            let mid = (low + high)/2
            if num == dots[mid] {
                return mid
            } else if num < dots[mid] {
                high = mid-1
            } else {
                low = mid+1
            }
        }

        return nil
    }

    var sameDots = 0
    for i in 0..<n {
        for m in i+1..<n {
            let distance = dots[m] - dots[i]
            if search(dots[m] + distance) != nil {
                sameDots += 1
            }
        }
    }

    print(sameDots)
}

투포인터?

for _ in 0..<Int(readLine()!)! {
    let n = Int(readLine()!)!
    let dots = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by: <)
    
    var sameDots = 0
    for center in 0..<n {
        var low = 0
        var high = n-1
        
        while low < high {
            let lowDist = dots[center] - dots[low]
            let highDist = dots[high] - dots[center]
            
            if lowDist == highDist {
                sameDots += 1
                low += 1
            } else if lowDist > highDist {
                low += 1
            } else {
                high -= 1
            }
        }
    }
    print(sameDots)
}

 

배운점

이 문제도 이분 탐색인 걸 알았는데도 어떻게 접근해야할지 몰라서...

200_000_000 의 배열에다가 먼저 점을 다 체크하고 0을 가운데인 100_000_000으로 해서 치환시켜서 계산을 해보려고 했는데 범위가 범위다 보니 당연히 시간초과가 났다.

두 번째 점까지도 이미 n^2인데 나머지 하나를 다 뒤져서 찾는 게 많이 비효율적으로 느껴졌던 것 같다.. 경우에 따라서 n^2도 효율적인 풀이가 될 수 있으니 너무 겁먹지 말자 !!