[프로그래머스] 저울 - 그리디(greedy)

1. 문제 설명

 

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 합니다. 이 저울의 양팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같습니다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있습니다.

 

 

저울추가 담긴 배열 weight가 매개변수로 주어질 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

예를 들어, 무게가 각각 [3, 1, 6, 2, 7, 30, 1]인 7개의 저울추를 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21입니다.

 

---

2. 제한 사항

 

• 저울추의 개수는 1개 이상 10,000개 이하입니다.
• 각 추의 무게는 1 이상 1,000,000 이하입니다.

---

3. 입출력 예

weight	return
[3, 1, 6, 2, 7, 30, 1]	21

 

---

4. 나의 풀이

저울을 활용한 유형은 computing thinking 할 때에나 AI 역량검사 시 게임으로 자주 나온다. 코딩 문제로 푸는 것은 처음인데, 어떻게 풀지 감이 안와서 손으로 먼저 풀어보았다. 우선, 무게 리스트를 내림차순으로 정렬하고 무거운 것부터 무게추를 이용하도록 코드를 짜보았다.

 

def solution(weight):
    answer = 0
    weight.sort(reverse = True)
    
    i = 1          #무게 1부터 확인
    while(True):
        temp = i
        for j in weight:
            if j <= temp:
                temp -= j
                if temp < 0:
                    return i
                elif temp == 0:
                    i += 1
                    continue
        if temp != 0:
            return i
            
    return answer

 

무게추를 써가면서 필요한 무게가 0이 되면, i 를 하나씩 늘려가며 불가능한 경우가 나올때까지 반복문을 돌렸다. 이중 반복문에 많은 조건문을 썼기 때문에 효율성 테스트는 기대를 안하고 돌렸는데

 

 

 

o_o ,,,,, 역시나 였다. 이전에 푼 문제를 약 2시간 고민해서 풀었지만, 시간을 과도하게 써서 얻은 교훈이 있기 때문에, 다른 사람의 풀이를 찾아보고 코드 리뷰를 해보기로 하였다.

 

def solution(weight):
    # 1. weight를 오름차순으로 정렬합니다.
    weight = sorted(weight)
    
    # 2. answer 1부터 시작합니다. 추의 최소 무게는 1입니다.
    answer = 1
    
    # 3. weight를 순회합니다.
    for w in weight:
    
        # 1. answer >= w라면, answer에 w를 더해줍니다.
        if answer >= w:
            answer += w
            
    # 4. answer를 반환합니다.
    return answer

 

추들의 무게의 합 + 1 = 추들이 측정할 수 없는 최소 무게

을 이용한 풀이이다. 주어진 추가 1, 1, 2 일때, 1은 1로 , 2는 1+1 또는 2로, 3은 1+2로, 4는 1+1+2로 표현이 가능하다. 하지만 5는 표현이 불가하다. 따라서 추 무게의 합이 답이 될 수 있는 최소값이라는 것이다.

 

해당 풀이를 이용하면 매우 깔끔하게 문제가 풀린다. 사람이 직관적으로 문제를 해결하는 방법을 일반화시켜 코드로 작성하는 것이 가장 일반적인 접근법이라고 생각했지만, 한계가 있다는 것을 이번 기회에 깨달았다...

 

 

 

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

코딩테스트 연습 - 저울