[프로그래머스/JAVA] 코딩테스트 연습 > 연습문제 > 귤 고르기 (by 다알쥐AI)

[귤 고르기] 코딩테스트 연습 > 연습문제 > 귤 고르기

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

 

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

 

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

---

입출력 예

---

입출력 예 설명

입출력 예 #1

• 본문에서 설명한 예시입니다.

입출력 예 #2

• 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

입출력 예 #3

• 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

---

[간단설명]

k개 만큼 귤을 담을 때, 귤 종류의 최소값 구하기

 

[접근방법]

1. 리스트를 만들고, 초기화한다.

2. 리스트에 귤의 개수를 기록한다.

3. 리스트를 귤의 개수 내림차순 정렬한다.

4. k에서 귤의 개수를 빼주면서, 귤의 종류를 카운트 한다.

5. 귤 종류 최소값 리턴

 

[주의사항]

- 귤의 길이보다, 귤의 원소가 큰 경우를 고려하자(런타임 오류)

- 귤의 개수를 내림차순 정렬하는 것이 이 문제의 핵심이다.

ㄴ List를 사용해도 좋고, Map을 사용해도 좋다,

ㄴ 본인에게 편한 방법을 사용하자.

 

[소스공개]

import java.util.*;
class Solution {
    // 아이템 클래스
    class Item{
        // 인덱스, 번호
        int index;
        int number;
        // 생성자
        public Item(int index,int number){
            this.index=index;
            this.number=number;
        }
        // Number게터
        public int getNumber(){
            return this.number;
        }
        // Number세터
        public void setNumber(int number){
            this.number=number;
        }
    }
    public int solution(int k, int[] tangerine) {
        // 아이템 리스트
        List<Item> list = new ArrayList<>();
        // 리스트 초기화(원소 최대값=10000000)
        for(int i=0;i<=10000000;i++){
            Item item = new Item(i,0);
            list.add(item);
        }
        // 귤 사이즈만큼 반복
        for(int t :tangerine){
            // 리스트에 귤 개수 추가
            list.get(t).setNumber(list.get(t).getNumber()+1);
        }
        
        // 귤 개수가 큰 순서로 정렬(내림차순)
        Collections.sort(list,new Comparator<Item>(){
            @Override
            public int compare(Item o1, Item o2){
                return o2.number - o1.number;
            }
        });
        
        // 종류별 귤 개수
        int count=0;
        // k에서 귤개수를 빼준다
        for(Item i : list){
            k-=i.getNumber();
            count++;
            if(k<=0){
                break;
            }
        }
        // 최소값 리턴
        return count;
    }
}

 

[실행결과]