<다시풀기성공>[프로그래머스] lv2 귤고르기 / JAVA

 

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

---

코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        /*
        1. 배열을 순회하며 하나씩 Map에 넣으면 시간복잡도는 n^2 이된다.
        2. 먼저 정렬하면 n, 순회하며 비교하며 Map에 넣으면 n, Map 에서 찾는것 n 
            -> 시간복잡도 n
        */
        
        /*
        1. Arrays.sort(tangerine)
        2. 배열 끝까지 순회하며 비교해서 카운트 증가 후 Map 에 저장
        3. Map 에서 가장 value 높은것 부터 찾아서 k와 뺄셈하여 k가 0이 되는 순간을 찾음
        4. 결과 배열을 만들어서 반환
        */
    int answer = 0;
    Arrays.sort(tangerine);
    List<Integer> list = new ArrayList<>();
    int tmp = tangerine[0];
    int count = 1;
    int loopCount = 0;
    for (int i = 1; i < tangerine.length; i++) {
      if (tmp != tangerine[i]) {
        tmp = tangerine[i];
        list.add(count);
        count = 1;
      } else if (i == tangerine.length - 1) {
        list.add(++count);
      } else {
        count++;
      }
    }

    int max = 0;
    int idx = 0;
    while (list.size() > 0) {
      for (int i = 0; i < list.size(); i++) {
        max = 0;
        if (max < list.get(i)) {
          max = list.get(i);
          idx = i;
        }
      }
      k -= list.get(idx);
      list.remove(idx);
      if (k <= 0 && loopCount == 0) {
        answer = 1;
        break;
      } else if (k <= 0) {
        break;
      }
      answer++;
      loopCount++;
    }
    return answer;
    }
}

한시간 가량 걸려서 나름대로 열심히 풀었으나 또 실패했다. 

스트레스가 극심해서... 머리가 멈춰버렸다.ㅋㅋㅋ

 

주어진 대표 3가지 테스트케이스는 통과했는데 나머지가 안된다.

 

4, 14, 16, 19, 20, 31, 32 만 통과했다.

 

 

---

다른 분들의 풀이를 배워보자

https://hjdiary.tistory.com/9

[프로그래머스] 프로그래머스 귤 고르기 JAVA 자바 풀이

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        Map<Integer, Integer> m=new HashMap<>();
        
        for(int t:tangerine){
            m.put(t,m.getOrDefault(t, 0)+1);
        }

        List<Integer> list=new ArrayList<>(m.values());
        Collections.sort(list, Collections.reverseOrder());
        
        for(Integer a:list){
            k-=a;
            answer++;
            if(k<1){
                return answer;
            }
        }
        
        return answer;
    }
}

나와 비슷한 로직을 생각하신 것 같다. 

 

 

 

---

다시 풀어보기

23.03.10

다른 문제들을 풀며 논리력이 향상된 것인지 다시 풀어봤는데 빠르게 성공했다.

다른 분의 코드라던가 전혀 영향없이 온전히 스스로 해내서 기분이 좋다.

 

코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        
        int answer=1;
        
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(tangerine);
        int count=1;
        int tmp=0;
        for(int i=0; i<tangerine.length-1; i++){
            if(tangerine[i]==tangerine[i+1]){
                count++;
            }
            else{
                list.add(count);
                count=1;
            }
        }
        list.add(count);
        
        list.sort(Comparator.reverseOrder());
        
        for(int item : list){
            k=k-item;
            if(k<=0){
                return answer;
            }
            answer++;
        }
        
        return answer;
        
    }
}

같은 종류인 귤의 개수가 중요하므로 이를 ArrayList에 담았고

이 ArrayList를 내림차순으로 정렬 후, 주어진 k와 비교하는 방식으로 최소 귤 종류의 개수를 알 수 있다.

 

25분 정도 소요되었다.