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

문제

- 문제 링크: 귤 고르기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: tangerine의 길이

- counter에 귤의 개수를 저장하는 시간 복잡도는 O(N)

- 귤의 개수만 다시 sorted_counts에 넣고 내림차순으로 정렬: O(NlogN)

- 반복문은 최악의 경우 모든 원소를 순회하므로 시간 복잡도는 O(N)

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

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int solution(int k, vector<int> tangerine) {
    // 크기에 따른 귤의 개수를 세는 counter
    unordered_map<int, int> counter;
    
    // 크기별로 귤의 개수를 셈
    for (int i = 0; i < tangerine.size(); ++i) {
        counter[tangerine[i]]++;
    }
    
    // 각 귤의 개수만 저장 후 내림 차순 정렬
    vector<int> sorted_counts;
    for (const auto& kv: counter) {
        sorted_counts.push_back(kv.second);
    }
    sort(sorted_counts.rbegin(), sorted_counts.rend());
    
    int num_types = 0; // 현재까지 고른 귤의 종류
    int count_sum = 0; // 현재까지 귤 개수의 총 합
    
    // 가장 많은 귤의 개수부터 순회
    for (int count : sorted_counts) {
        count_sum += count;
        num_types++;
        
        // 귤의 개수 합이 k 이상되면 종료
        if (count_sum >= k) {
            break;
        }
    }
    return num_types;
}

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