[프로그래머스] 138476번 - 귤고르기

1. 문제 및 예제

 

 담은 귤의 종류가 적다는건 갯수가 많은 종류를 순서대로 나열해 순서대로 박스에 넣어주면 된다. 귤의 종류와 그 갯수를 저장할 자료구조 하나 그리고 그것을 갯수로 정렬할 알고리즘을 생각하면 별로 어렵지 않은 문제이다. C++의 sort()를 사용했으니 시간복잡도는 O(NlogN)이다.

---

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

프로그래머스

---

2. 풀이과정

 

 처음 내가 이 코드를 작성하고 제출을 했을 때 분명 더 좋은 풀이법이 있을거라 생각했지만, 검색해보니 다들 비슷하게 푼 것 같다. 내가 사용한 방법은 map자료구조에서 vector로 옮기고 compare함수를 만들어 value값을 기준으로 내림차순으로 정렬해주었다. 사용한 map자료구조에서 vector자료구조로 옮기는 과정이 자원 낭비라고 생각했지만 다른 방법이 없나보다... ㅠㅠ 다음은 내 코드이다.

 

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    map<int, int> m;
    
    
    for(auto num : tangerine){
        if(m.find(num) == m.end()){
            m.insert(make_pair(num, 1));
        }else{
            m[num]++;
        }
    }
    
    vector<pair<int,int>> vec( m.begin(), m.end() );
    sort(vec.begin(), vec.end() , cmp);
    
    int index = 0;
    
    while(k > 0){
        answer++;
        k -= vec[index].second;
        index++;
    }
    
    return answer;
}