사용자 도구

사이트 도구


ps:problems:programmers:43236

징검다리

ps
링크https://programmers.co.kr/learn/courses/30/lessons/43236
출처프로그래머스
문제 번호43236
문제명징검다리
레벨Level 4
분류

파라메트릭 서치

시간복잡도O(mlogn)
인풋사이즈n<=1,000,000,000, m<=50,000
사용한 언어Python
해결날짜2020/12/31

풀이

  • 파라메트릭 서치로 푸는 문제.
  • “제거할 돌의 갯수가 n일때의 거리의 최솟값 중 최댓값=x를 구하라” 가 원래 문제인데, 이걸 파라메트릭 서치 형태로 바꾸기 위해서 f(x)를 “거리의 최솟값이 x일때 제거할 돌의 최소 갯수” 또는 “모든 거리를 x보다 크게 만들기 위해 제거해야 하는 돌의 최소갯수” 라고 정의한다. 그러면 x가 커질수록 f(x)도 커진다. 이제 풀어야 하는 문제는 “f(x) ⇐ n 인 x의 최댓값을 [1, 1,000,000,000] 범위 안에서 구하라”가 된다
    • n이 픽스된 상황에서 x의 범위를 구하는 문제를, 결정 문제로 바꾸는 과정에서는 x가 픽스된 상황에서 n의 범위를 체크하는 문제가 되다 보니 조금 헷갈리긴 한다.
  • f(x) 를 구하는 것은, 앞에서부터 이전 돌의 위치부터 현재 돌의 거리가 x보다 작으면 현재 돌을 제거하는 방식으로 그리디하게

O(m)에 구할 수 있다 (m은 돌의 갯수)

  • 이분탐색 구간의 상한은, distance / {남은돌의 갯수} 이다.
  • 따라서 총 시간 복잡도는 O(mlogn)이 된다 (n=distance)

코드

"""Solution code for "Programmers 43236. 징검다리".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43236
- Solution link: http://www.teferi.net/ps/problems/programmers/43236
"""

from teflib import algorithm


def solution(distance, rocks, n):

    def predicate(min_dist):
        prev_rock = 0
        removed_rock_count = 0
        for rock in rocks:
            if rock - prev_rock >= min_dist:
                prev_rock = rock
            else:
                removed_rock_count += 1
        if distance - prev_rock < min_dist:
            removed_rock_count += 1
        return removed_rock_count > n

    rocks.sort()
    return algorithm.binary_search(0, distance, predicate) - 1

토론

댓글을 입력하세요:
V U P F U
 
ps/problems/programmers/43236.txt · 마지막으로 수정됨: 2021/06/04 16:59 저자 teferi