[프로그래머스] 저울 (Java)

프로그래머스 저울

문제풀이

이 유형의 문제는 직접 예제를 손으로 풀어가면서 규칙성을 찾아내야한다. 이런 문제에 너무 약해서 연습이 많이 필요한 것 같다.

1. 누적합을 이용하기 위해 배열을 오름차순으로 정렬한다.
2. 배열의 인덱스 0부터 다음을 수행한다.
   • answer >= 현재 무게 추의 무게(w)일 때 answer += w
   • answer < 현재 무게 추의 무게(w)일 때 break
3. `return answer``

[1, 1, 2, 3, 6, 7, 30]의 무게 추가 주어졌을 때 직접 수행해보면

• i = 0
  answer = 1, w = 1
  answer >= w
  answer += w
  answer = 2
• i = 1
  answer = 2, w = 1
  answer >= w
  answer += w
  answer = 3
• i = 2
  answer = 3, w = 2
  answer >= w
  answer += w
  answer = 5
• i = 3
  answer = 5, w = 3
  answer >= w
  answer += w
  answer = 8
• i = 4
  answer = 8, w = 6
  answer >= w
  answer += w
  answer = 14
• i = 5
  answer = 14, w = 7
  answer >= w
  answer += w
  answer = 21
• i = 6
  answer = 21, w = 30
  answer < w
  return 21

각 단계에서 answer 미만의 무게는 모두 만들 수 있음을 알 수 있고 만들 수 있는 무게의 최댓값은 answer - 1이다. 따라서 answer < w일 때 answer는 만들 수 없는 무게의 최솟값이 된다.

구현코드

import java.util.*;

class Solution {
    public int solution(int[] weight) {
        Arrays.sort(weight);
        
        int answer = 1;
        for(int i = 0 ; i < weight.length ; ++i){
            int w = weight[i];
            if(answer >= w) answer += w;
            else break;
        } 
        return answer;
    }
}