[프로그래머스 Lv.4] N으로 표현 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43236

풀이

아래와 같이 먼저 단순하게 생각할 수 있는 방법으로 풀이해 보았다. 하지만 역시나 시간 초과로 인해 실패하였고, 이는 아래 풀이처럼 완전 탐색을 사용했을 때 탐색해야 하는 데이터가 너무 많기 때문이다.

징검다리를 이루는 돌의 수가 최대 5만개이고, 제외할 수 있는 돌의 수도 5만 개 이하기 때문에 최악의 경우 5만 개 중 2만 5천 개의 돌을 제외하는 조합을 모두 계산해야 한다. 이는 정말 말도 안 되는 수이다. (단순히 생각해 봐도 50000!/(50000-25000)! 이니까 50000부터 25000까지 곱한 값이다. 대충 3만을 25000번 곱했다고 봐도 (3*10^4)^25000 = 3^25000 * 10^(4*25000) = 3^25000 * 10^100000이다.)

그렇기에 아래와 같은 완전 탐색으로는 풀 수 없으므로 다른 방법을 생각해봐야한다.

from itertools import combinations

def solution(distance, rocks, n):
    answer = 0
    rocks.extend([0, distance]) # 시작점과 끝지점의 돌을 추가
    
    for comb in combinations(rocks, n): # n개의 제외할 돌의 조합을 선정
        new_rocks = sorted([rock for rock in rocks if rock not in comb]) # 선택된 돌들을 제거하고 이들을 정렬
        
        min_distance = distance
        for i in range(len(new_rocks) - 1): # 돌들의 거리를 계산
            min_distance = min(min_distance, new_rocks[i+1] - new_rocks[i]) # 최솟값 저장
        answer = max(answer, min_distance) # 최솟값들의 최대값 갱신
        
    return answer

4단계 문제답게 문제를 보고 바로 생각나는 단순한 아이디어로는 이 문제를 풀 수가 없다. 거리를 기준으로 보지 않고, 거리라는 목표를 이루기 위해 바위를 얼마나 제외해야 하는지를 기준으로 문제를 풀어나가야 한다.

예를 들어, 4라는 정답을 만들어 내기 위해서는 몇 개의 바위들을 제외하여 다른 바위 간의 거리가 4보다 크도록 만들면 된다. 만약 2라는 정답을 만들어 내려면, 아무런 바위도 제외하지 않아도 된다.

 

위의 예시에서 살펴볼 수 있듯이 제거해야 할 바위의 수가 목표보다 적다면 제거해야 할 바위의 수를 늘려야 하기에 거리를 짧게 만들면 되고, 반대로 제거해야 할 바위의 수가 목표보다 크다면 제거해야 할 바위의 수를 줄여야 하기에 거리를 길게 만들면 된다. 그리고 이 방법을 답을 찾을 때까지, 즉 목표한 바위의 수만큼 제외될 때까지 이진 탐색으로 반복하면 된다.

 

def solution(distance, rocks, n):
    rocks.sort() # 징검다리에서 각 바위 사이의 거리를 계산해야 하기에 오름차순으로 정렬
    
    low, high = 0, distance        
    answer = 0
    while low <= high:
        mid = (low + high) // 2
        
        if check_not_enough(mid, rocks, n, distance): # 현재 지정한 거리가 원하는 숫자 이상의 바위를 제거하기에 충분하지 않다면 mid를 감소시켜, 더 많은 바위를 제거할 수 있도록 변경 
            high = mid - 1
        else: # 거리가 이미 숫자를 충족한다면, 거리를 늘려 더 적은 수의 바위가 제외되도록 변경
            answer = mid
            low = mid + 1
    
    return answer

def check_not_enough(dist, rocks, n, last):
    removed_rocks = 0
    temp = 0
    
    for rock in rocks:
        if rock - temp < dist: removed_rocks += 1 # 원하는 거리보다 두 바위 사이의 간격이 짧으므로 해당 바위를 제거해줘야 함
        else: temp = rock   
    if last - temp < dist: removed_rocks += 1 # 가장 마지막 돌, 즉 도착점과 그 전 바위도 비교해줘야함
    if removed_rocks > n: # 제거된 바위의 수가 정해져 있는 제거할 바위의 수보다 크다면 제거된 바위의 수를 줄여야 하기에 dist를 더 크게 해야함
        return True
    return False