[프로그래머스] 귤고르기

package org.example.알고리즘.귤고르기;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(6, new int[]{1, 3, 2, 5, 4, 5, 2, 3});
        System.out.println("================================");
        solution.solution(4, new int[]{1, 3, 2, 5, 4, 5, 2, 3});
        System.out.println("================================");
        solution.solution(2, new int[]{1, 1, 1, 1, 2, 2, 2, 3});
    }
    
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        Map<Integer, Long> collected = Arrays.stream(tangerine)
                .boxed()
                .collect(Collectors.groupingBy(x -> x, Collectors.counting()));
        
        List<Map.Entry<Integer, Long>> collect = collected.entrySet().stream()
                .sorted(Map.Entry.<Integer, Long>comparingByValue().reversed())
                .collect(Collectors.toList());
        
        while (k > 0) {
            System.out.println("collect = " + collect.get(0));
            long value = collect.get(0).getValue();
            k -= (int) value;
            answer++;
            collect.remove(0);
        }
        
        return answer;
    }
}

• 일단 그룹화와 정렬문제이다.
  • 더 효율적으로 풀 수 있을 것 같긴한데, 굳이 좋은 그루핑, 정렬 함수가 있는데 안쓸 이유가 없다.

Arrays.stream(tangerine)
                .boxed()

• 귤을 스트림화한다. 이후 귤에 자체 int 값에 대해서는 그룹핑이 불가능하기에 별도 박싱을 수행한다.

.collect(Collectors.groupingBy(x -> x, Collectors.counting()));

• 박싱된 각 값의 시간복잡도 O (n)
  • 에 더하여 각 Integer 값을 내부적으로 HashMap 화를 통해 각 키값(정수) 에 대해 카운트를 수행한다.
    • 각각 boxed 와 collect 는 각각 O(n) 의 시간복잡도가 아니라
    • 스트림자체의 지연평가때문에 결국 O(n) 의 효율을 가지게 된다.

      💡

      지연평가?
      
      필요한 부분만 계산하는 행위이다.
      
      예를들어 collect에서 요소 하나하나가 그룹핑되는 과정에서 별도 박싱이 수행 → 이후 하나의 요소에 대한 collect 가 수행되는 것이다.
      

collect = 2=2
collect = 3=2
collect = 5=2

• 이런식으로 각 값에 대해 키 - 밸류 값으로 카운트가 담긴Map 을 반환하게 된다.

collected.entrySet().stream()

• 그루핑된 해시맵에 별도 순회가 필요하다
  • entrySet 을 통하여 해시맵 내부의 버킷배열을 순회한다.
    • 각 버킷에 있는 연결리스트 혹은 트리 구조 ( 상황에 따라 구조가 달라짐 )
    • 을 확인하여 해당 값과 버킷배열의 값을 키 : 밸류 값의 Entry 객체로 들고온다,

.sorted(Map.Entry.<Integer, Long>comparingByValue().reversed())

• 소팅이다.
  • Entry 객체에 대해 각각 값을 valuee 를 기준으로 비교한다.

    (c1, c2) -> c1.getValue().compareTo(c2.getValue());

    • 내부적으로는 일반적인 Comparator ..상의 정수 반환과 동일하다.

  reserved() 를 통하여 역방향으로 정렬

  • 내림차순 반환으로 큰 카운트를 가진 key 가 제일 앞에 온다

`while (k > 0) {
            System.out.println("collect = " + collect.get(0));
            long value = collect.get(0).getValue();
            k -= (int) value;
            answer++;
            collect.remove(0);
        }

• collect 첫번째 entry 를 깐다
  • entry 의 value 만큼 귤갯수를 차감하며
  • 종류로 하나 추가해준다
  • 이후에 해당 엔트리는 제거한다. ( 시간복잡도 상수시간 )

최종 시간복잡도 O(n)

Uploaded by N2T