본문 바로가기
알고리즘 문제 풀이/그리디

Minimum Subsequence in Non-Increasing Order

by 가나무마 2021. 4. 8.
728x90


배열에서 숫자를 뽑아서 리스트를 만들었을 때 뽑은 숫자는 배열에서 사라진다.
리스트의 총합이 배열의 총합보다 커지는 경우를 구하시오.
단, 답이 여러개면 최소 값을 구하시오.

답지 보기 전에 푼 거.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        //주어진 배열
        int[] array = nums;                
        //배열의 원소들을 크기 순서대로 정렬
        Arrays.sort(array);                
        //배열의 총합을 arraySum의 대입
        int arraySum = Arrays.stream(array).sum();        
        //숫자를 뽑아서 저장할 리스트 생성.
        List list = new ArrayList();                    
        //리스트의 총합으로 사용할 변수 초기화.
        int listSum = 0;                                

        //배열에서 크기 순으로 정리했기 때문에 마지막 요소(최댓값)부터 더해야하므로
        //배열의 접근 인덱스는 마지막 요소부터 접근함. == (int i = array.length-1)
        for (int i = array.length-1; i >= 0; i--) {        
            int temp = array[i];
            //리스트에 배열에 배열의 요소를 더해줌.
            list.add(temp);                    
            //리스트의 총합에 해당 값을 더함.
            listSum += temp;                
            //배열의 총합에 해당 값을 뺌. 
            arraySum -= temp;                
            //리스트의 총합보다 배열의 총합이 커지면 반복문 종료.
            if (listSum > arraySum) {        
                break;
            }
        }

        return list;                        //결과 리스트를 리턴해줌.
    }
}

그냥 생각나는대로 단순하게 문제가 하라는대로 풀었습니다.
리스트에서 최댓값부터 뽑아야 배열의 총합보다 빨리 커지기 때문에 최댓값부터 리스트에 넣었습니다.

리트코드 최다 추천 글

public List<Integer> minSubsequence(int[] nums) {
    List<Integer> res = new ArrayList<>();
    var pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    int sub_sum = 0, total_sum = 0;
    for (var n : nums) {
        pq.offer(n);
        total_sum += n;
    }
    while (sub_sum <= total_sum / 2) {
        res.add(pq.peek());
        sub_sum += pq.poll();
    }    
    return res;
}

우선순위 큐를 사용하였고, 내림차 순으로 큐에 넣었음.

728x90
반응형