[프로그래머스, JAVA] 저울

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

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

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

제한 사항

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

입출력 예

weightreturn

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

21

 

1. 풀이 방법

이 방법은 구현능력이라기 보다는 아이디어에 어렸을때 추 가지고 영재교육 받았으면 유리했을듯한 문제 같네요..
시간초과로 검색해봤더니 결국 아이디어 문제였네요.. 

총합 0으로 초기화

1) 첫 번째 추 총합에 더하기 두번째 인덱스 부터 반복

2) 두 번째 인덱스부터 현재 인덱스가 가리키는 값이 총합 + 1과 같거나 작으면 총합에 더하기
BUT 크다면 반복문 종료 후 총합 + 1 반환

import java.util.Arrays;

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