[PCCP] Lv2: 귤 고르기(138476) 해설

문제

- 문제 링크: 귤 고르기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: tangerine의 길이

- 해시맵으로 개수를 구하고 리스트로 만들어서 정렬: O(NlogN)

- 반복문은 최악의 경우 모든 원소를 순회: O(N)

- 최종 시간 복잡도: O(NlogN)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Solution {
    public int solution(int k, int[] tangerine) {
        // 귤의 개수를 세는 HashMap 객체 생성
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : tangerine) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        
        // 개수를 내림차순으로 정렬
        ArrayList<Integer> sortedCounts = new ArrayList<>(map.values());
        sortedCounts.sort(Collections.reverseOrder());
        
        int numTypes = 0; // 현재까지의 종류 수
        int countSum = 0; // 현재까지의 귤 개수 합
        
        for (int count: sortedCounts) {
            countSum += count;
            numTypes++;
            // 귤 개수 합이 k 이상이 되는 순간 종료
            if (countSum >= k)
                break;
        }
        return numTypes;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: tangerine의 길이

- Counter를 만들고 정렬: O(NlogN)

- 반복문은 최악의 경우 모든 원소를 순회: O(N)

- 최종 시간 복잡도: O(NlogN)

from collections import Counter

def solution(k, tangerine):
    # 귤의 개수를 세는 Counter 객체 생성
    counter = Counter(tangerine)
    
    # 개수를 내림차순으로 정렬
    sorted_counts = sorted(counter.values(), reverse=True)
    
    num_types = 0 # 현재까지의 종류 수
    count_sum = 0 # 현재까지의 귤 개수 합
    
    for count in sorted_counts:
        count_sum += count
        num_types += 1
        
        # 귤 개수 합이 k 이상이 되는 순간 종료
        if count_sum >= k:
            break
    return num_types

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: tangerine의 길이

- counter를 만들고 정렬: O(NlogN)

- 반복문은 최악의 경우 모든 원소를 순회: O(N)

- 최종 시간 복잡도: O(NlogN)

function solution(k, tangerine) {
    // 귤의 개수를 세는 counter 오브젝트 생성
    const counter = {};
    for (const t of tangerine) {
        counter[t] = (counter[t] || 0) + 1;
    }
    
    // 개수를 내림차순으로 정렬
    const sortedCounts = Object.values(counter).sort((a, b) => b - a);
    
    let numTypes = 0; // 현재까지의 종류 수
    let countSum = 0; // 현재까지의 귤 개수 합
    
    for (const count of sortedCounts) {
        countSum += count;
        numTypes += 1;
        
        // 귤 개수 합이 k 이상이 되는 순간 종료
        if (countSum >= k) {
            break;
        }
    }
    
    return numTypes;
}

solution 2)

import

solution 3)

import