프로그래머스 - 저울

분류 : Greedy Algorithm (탐욕 알고리즘)

사용언어 : Python3

문제 분석

주어진 weight list에 대하여 자신이 만들 수 있는 모든 숫자의 조합을 통하여 측정할 수 있는 무게의 최댓값을 구하는 문제이다.

example

[3, 1, 6, 2, 7, 30, 1] 의 무게를 가지는 추가 있을 때 측정할 수 있는 최대 무게는 21이다.

문제 접근

가장 처음에 생각해 낸 해결법은 무게 순으로 정렬한 후 해당 무게에 대하여 가능한 모든 경우의 수를 구하는 것이었다.

예를 들어, 위의 weight에 대하여 정렬을 수행한다면

weight = [1, 1, 2, 3, 6, 7, 30] 이 될 것이다.

이 때, 가장 앞에 있는 수부터 순서대로 꺼내와 가능한 모든 수의 조합을 list 안에 저장하며 중복되는 경우는 저장하지 않는다.

문제 접근

해당 경우와 같이 모든 경우에 대하여 탐색을 수행하며 문제를 풀어나갈 경우 정확한 답을 얻을 수 있지만 너무나 당연하지만 시간초과가 나타난다.

먼저 선형적으로 모든 요소에 접근한 후 중간에 저장되어 있는 모든 결과에 대하여 다시 연산을 수행하기 때문에 나타나는 결과이다.

이후, 이를 어떻게 해결해나갈지에 대하여 다시 고민을 하게 되었고 여러가지 테스트를 하던 중 흥미로운 점을 발견하였다.

정렬되어 있는 리스트를 다시 확인한 후 시간 초과가 나타나는 코드에서 실행 중간 실행결과를 확인해보았다.

weight = [1, 1, 2, 3, 6, 7, 30]

중간 결과

결과 값을 확인해보면, 21 이후 바로 30으로 넘어가며 해당 부분에서 miss가 발생하는 것을 확인할 수 있다.

그리고 너무나 당연하게도 이 문제에서 가장 작은 추의 무게가 2라면 정답은 당연히 1이 된다는 것이었다.

이 두 가지의 상황을 종합하여 하나의 가설에 도달하게 되었다.

이전까지의 모든 추의 무게의 합이 다음 추의 무게보다 작다면 해당 무게는 측정 불가능하다.

해당 가설로 테스트를 진행한 결과 문제를 해결할 수 있었고, 중간에 다음과 같은 수정 및 보완 작업을 수행하였다.

  1. weight = [1, 1, 3]인 경우

    해당 상황에서 위의 가설로 문제를 풀 경우 정답은 2로 출력이 된다.

    이를 해결하기 위하여 중간 합에 +1을 해주었다.

  2. 모든 조건을 만족할 경우

    해당 상황에서는 현재까지의 모든 추의 합에 대하여 +1을 하여 정답을 출력하여 문제를 해결하였다.

문제 풀이

def solution(weight):
    answer = 0
    weight.sort()
    result = 1
    for w in weight:
        if w > result + 1:
            return result
        result += w
        

    return sum(weight) + 1