코딩 테스트/Level 3

금과 은 운반하기

컴닥 2021. 10. 8. 12:28
반응형

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

 

코딩테스트 연습 - 금과 은 운반하기

어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는

programmers.co.kr

 

블로그에서 다룬 적 있다. 

https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search

 

32. 이진 검색(Binary Search), 파이썬

정렬된 데이터에서 검색할 때는 이진(이분) 검색이 더 효율적입니다. 친구가 1부터 100까지 숫자 중 하나를 고르고, 나는 그 숫자를 맞추는 게임을 한다고 가정합니다. 친구는 "고른 숫자가 내가

comdoc.tistory.com

주어진 시간 내에 도시 건설에 필요한 금과 은을 배송할 수 있는가?
라고 문제를 바꾸고 이분 검색을 쓰자... 

def solution(n_gold, n_silver, golds, silvers, weights, times):
    def deliver(time_limit):
        gold = silver = total = 0
        for i in range(len(golds)):
            # 편도 횟수
            one_way = time_limit // times[i]
            # 배달 횟수 = 왕복당 1회 + 1이 남으면 1 추가
            deliver_num = one_way // 2 + one_way % 2
            # 총 배송 가능 무게
            weight = deliver_num * weights[i]
            # 금만 보냈을 때 배송 가능한 금
            gold += min(golds[i], weight)
            # 은만 보냈을 때 배송 가능한 은
            silver += min(silvers[i], weight)
            # 배송 가능한 금과 은 모두!
            total += min(golds[i] + silvers[i], weight)
            # 금, 은, 모두가 배송 가능하면 True
        return gold >= n_gold and silver >= n_silver and total >= n_gold + n_silver

    end = answer = 10 ** 15
    start = 0
    while start <= end:
        mid = (start + end) // 2
        if deliver(mid):
            end = mid - 1
            answer = mid
        else:
            start = mid + 1
    return answer

필요한(needed, necessary) 이라는 의미로 변수명에 n을 사용했다. 
금, 은, 금과 은 모두가 배송가능해야 한다는 부분의 코드는 잘 떠오르지 않아서 다른 코드를 참고했다. 

테스트 1 〉	통과 (0.06ms, 10.3MB)
테스트 2 〉	통과 (0.06ms, 10.3MB)
테스트 3 〉	통과 (0.09ms, 10.3MB)
테스트 4 〉	통과 (0.11ms, 10.4MB)
테스트 5 〉	통과 (0.29ms, 10.3MB)
테스트 6 〉	통과 (0.51ms, 10.3MB)
테스트 7 〉	통과 (0.80ms, 10.3MB)
테스트 8 〉	통과 (2.40ms, 10.4MB)
테스트 9 〉	통과 (5.34ms, 10.3MB)
테스트 10 〉	통과 (8.96ms, 10.2MB)
테스트 11 〉	통과 (298.46ms, 11.3MB)
테스트 12 〉	통과 (662.78ms, 12.7MB)
테스트 13 〉	통과 (783.25ms, 13.7MB)
테스트 14 〉	통과 (1245.93ms, 15.1MB)
테스트 15 〉	통과 (1713.49ms, 16.4MB)
테스트 16 〉	통과 (1955.72ms, 17.8MB)
테스트 17 〉	통과 (2802.68ms, 21.3MB)
테스트 18 〉	통과 (3164.74ms, 22.4MB)
테스트 19 〉	통과 (2886.98ms, 22.4MB)
테스트 20 〉	통과 (2922.81ms, 22.3MB)
테스트 21 〉	통과 (2322.53ms, 22.3MB)
테스트 22 〉	통과 (2970.54ms, 22.3MB)
테스트 23 〉	통과 (2634.21ms, 22.3MB)
테스트 24 〉	통과 (0.10ms, 10.3MB)

프로그래머스 공식 블로그에 해설이 잘 나와 있다..
https://prgms.tistory.com/101

반응형