Coding Test

풀이방법

코드

import java.util.*;

import static java.util.stream.Collectors.reducing;

public class Solution {

    public int solution(int[] A) {
        // 몇번 등장하는지 카운터 함수를 구현하기 : K=elem, V=count
        Map<Integer, Integer> counter = new HashMap<>();
        myCount(counter, A);
        // 카운터 >> List >> 정렬 >> 같은숫자가 검출되면 뺸다 :: 다 한다음에 뺸 갯수 합치기
        List<Integer> countList = new ArrayList<>(counter.values());
        countList.sort(Comparator.reverseOrder());
        int target = countList.get(0) - 1;
        int answer = 0;//몇개 뺴줘야할지
        for (int i = 1; i < countList.size(); i++) {

            if(target == 0) {
                Integer remainCounts = countList.subList(i, countList.size())
                        .stream()
                        .reduce(Integer::sum)
                        .get();
                answer += remainCounts;
                break;
            }

            if (countList.get(i) > target) {
                answer += (countList.get(i) - target);
                countList.add(i,target);
                countList.remove(i + 1);
            }
            target = countList.get(i) - 1;
        }
        return answer;
    }

    private void myCount(Map<Integer, Integer> counter, int[] A) {
        Arrays.stream(A).forEach(elem -> {
            if (counter.containsKey(elem)) {
                counter.put(elem, counter.get(elem) + 1);
            } else {
                counter.put(elem, 1);
            }
        });
    }

import collections
import heapq


def countMinDel(arr):
    dict = collections.Counter(arr)
    sorted_dict = dict.most_common()
    target = sorted_dict[0][1] - 1
    result = 0

    for val, cnt in sorted_dict[1:]:
        if target == 0:
            for item in sorted_dict[1:]:
                result += item[1]
            return result
        if cnt > target:
            result += cnt - target
        target -= 1

    return result


def test(arr, expected):
    result = countMinDel(arr)
    if(result == expected):
        print('Pass')
    else:
        print(f'Failure, result  was {result}')


test([1, 1, 1, 2, 2, 2], 1)
test([5, 3, 3, 2, 5, 2, 3, 2], 2)
test([127, 15, 3, 8, 10], 4)

개선된 python 코드

import collections

def countMinDel(arr):
    dict = collections.Counter(arr)
    sorted_dict = dict.most_common()
    result = 0
    target = -1
    for val, cnt in sorted_dict:
        if target == -1:
            target = cnt - 1
        elif target == 0:
            result += cnt
        elif cnt > target:
            result += cnt - target
            target -= 1
        else:
            target = cnt - 1
    return result

def test(arr, expected):
    result = countMinDel(arr)
    if(result == expected):
        print('Pass')
    else:
        print(f'Failure, result  was {result}')

test([1, 1, 1, 2, 2, 2], 1)
test([5, 3, 3, 2, 5, 2, 3, 2], 2)
test([127, 15, 3, 8, 10], 4)

시간복잡도

공간복잡도