[프로그래머스] 징검다리 (Swift)

https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리

징검다리~!

 

각기 다른 간격으로 배치되어 있는 징검다리들 중 n개를 제거했을 때 간격의 최솟값들 중에 가장 큰 값을 반환하는 문제

 

접근방법

이번에는 이분탐색의 범위까지는 접근했지만 탐색하는 기준을 뭐로 해야할지 모르겠어서

블로그 탐색 후 힌트를 얻었다..ㅎ 모르겠으면 이렇게라도 배워야지..!

 

이분탐색 범위는 이번에도 역시 결과값의 범위다.

0~간격의 최대값 즉 distance

 

이걸 어떤 방법으로 탐색하냐가 문제였는데 핵심은 이렇다.

몇개의 돌을 제거해야 mid(가정한 간격)이 최소간격이 될 수 있는지

-> getNumOfRemovedStone 함수 (mid간격이 최소간격이 되려면 몇개의 돌을 제거해야하는지 반환)

를 구한다.

 

이 문제는 이분탐색으로 upper_bound를 구하는 문제다.

 

제거해야하는 돌의 개수가 n보다 크면 -> n보다 많이 지워야 하므로 -> 지금보다 덜 지워야함 -> 덜 지우면 최소간격은 줄어듬 -> mid 보다 작은 간격에 정답이 있음 -> end = mid-1 (작은 쪽에서 답 찾으러 이동)

 

제거하는 돌의 개수가 n보다 작으면 -> 지금보다 더 지울 수 있음 -> 더 지우면 최소간격 늘어남 -> mid 보다 큰 간격에 정답이 있음 -> start = mid+1

 

제거하는 돌의 개수가 n이면 -> n개만큼 지우면 해당 간격을 얻을 수 있지만 더 큰 간격을 얻을 가능성이 있음 -> mid보다 큰 간격에 정답이 있을 수도 있음 -> start = mid+1

 

이런식으로 이분탐색을 구현하고 while문은 start <= end 로 한다.

start == end가 됐을 때 이 값이 정답이라는 보장이 없기 때문이다. 이유는 아래에 적겠음

 

upper_bound의 특징일 수도 있는데 왜 이렇게 구현하는지 설명하기 위해 예시를 들어보면

end를 반환하는 이유

[..., 3, 3, 4, ...] 배열이 있고 이 상태에서 3의 upper_bound 위치를 구한다고 하자.

이 상황에서 start 는 첫번째 3의 위치, end 는 두번째 3의 위치에 있다고 하면

mid는 start를 가리키고, [mid]는 3과 같으므로 start = mid+1 을 적용하여

start와 end 모두 두번째 3을 가리킨다.

또 한번 반복문을 돌면 이번에도 [mid] == 3 이므로 start는 4를 가리킨다.

반복문은 종료된다.

start가 end를 넘어왔다는 것은 start가 바로 전에 위치했던 자리가 3의 마지막 위치라는 것을 의미한다.

따라서 그 자리를 가리키고 있는 end를 리턴하면 정답이다. (이래서 start-1을 리턴해도 정답이 된다.)

 

while문 반복조건이 start <= end인 이유

[..., 3, 3, 4, ...] 배열이 있고, 이 상태에서 3의 upper_bound를 구하는 상황.

start는 두번째 3을 가리키고, end는 4를 가리키고 있다.

mid는 3을 가리키므로 start = mid+1 을 적용하여

start과 end 모두 4를 가리킨다. 이때 start와 end의 위치가 같다고 반복문을 종료하면

구하고자하는 3의 upper_bound가 아니라 4의 lower_bound위치를 반환하게 된다.

start 값에 mid+1, end 값에 mid-1을 대입할 경우, start와 end가 동일할 때에도 그 위치가 정답이 아닌 경우가 있다.

그렇기에 한번더 mid 위치의 값을 확인해서 4는 3보다 크므로 end = mid-1을 적용해야한다.

이때 end의 위치(start의 바로 전 위치)가 3의 마지막 자리이다.

 

휴 여전히 이 부분을 어려워하고 있는데 매번 경계값에 약하다는 걸 깨닫는 중

이렇게 손으로 차근차근 하다보면 나아지겠지!

 

소스코드

import Foundation

func getNumOfRemovedStone(_ minGap:Int, _ rocks:[Int]) -> Int {
    var here:Int = 0
    var removeCnt:Int = 0
    for rock in rocks {
        if rock - here < minGap {
            removeCnt += 1
        } else {
            here = rock
        }
    }
    return removeCnt
}

func solution(_ distance:Int, _ rocks:[Int], _ n:Int) -> Int {
    var answer:Int = 0
    let sortedRocks:[Int] = rocks.sorted()+[distance]
    
    var start:Int = 0
    var end:Int = distance
    var mid:Int = (start + end)/2
    
    while start <= end {
        mid = (start+end)/2
        
        let removeCnt:Int = getNumOfRemovedStone(mid, sortedRocks)
        if removeCnt > n {
            end = mid-1
        } else {
            start = mid+1
        }
    }
    return end
}

Swift 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int getNumOfRemovedStone(vector<int> rocks, int minGap) {
    int here = 0;
    int removeCnt = 0;
    for(int i = 0 ; i < rocks.size() ; i++) {
        if (rocks[i] - here < minGap) {
            removeCnt++;
        } else {
            here = rocks[i];
        }
    }
    return removeCnt;
}

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);
    
    int start = 0;
    int end = distance;
    int mid = (start+end)/2;
    
    while (start <= end) {
        mid = (start+end)/2;
        int removeCnt = getNumOfRemovedStone(rocks, mid);
        if (removeCnt > n) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    
    return end;
}

C++ 풀이

좌 Swift 우 C++

역시 속도..ㄷㄷ..

Swift는 Safe, Fast, Expressive..... Fast...?