귤 고르기

프로그래머스 - 귤 고르기

문제 요약

---

• 수확한 귤 중 k개를 골라 판매하려고 한다.
• 서로 다른 종류가 최소일 때 귤 종류의 수를 return

💡Idea

1. 같은 종류의 귤 개수를 어떻게 세야할까?
   → vector 에 종류, 개수를 저장하게 되면 탐색 불가능
   → kind(map) 에 귤 종류, 개수 저장 !
2. 어떻게 k개로 줄일까?
   → 귤의 종류가 적은 것부터 하나씩 빼자
   1) kind의 value 값으로 오름차순 정렬
   2) 귤 개수 - k 만큼 귤을 하나씩 빼기

Source Code

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    map <int, int> kind;
    for(int i=0; i<tangerine.size(); i++) {
        if(kind.find(tangerine[i]) == kind.end()) {
            kind.insert(make_pair(tangerine[i], 1));
        }
        else {
            kind[tangerine[i]]++;
        }
    }
   
    vector<pair<int, int>> result(kind.begin(), kind.end());
    sort(result.begin(), result.end(), compare);
    int cnt = tangerine.size() - k;
    answer = result.size();
       
    for(int i=0; i<result.size(); i++) {
        while(cnt > 0 && result[i].second > 0) {
            result[i].second--;
            cnt--;
        }
        if(result[i].second == 0) {
            answer--;
        }
        if(cnt == 0) break;
    }
   
    return answer;
}

Feedback

---

1. map 을 value 기준으로 정렬하는 부분에서 헤맴.
   → vector로 옮겨서 정렬하는 방법 생각하기 !

Remind

• kind에 있는 값들을 vector로 복사
  → vector<pair<int, int>> result(kind.begin(), kind.end());

• 두번째 인자로 정렬
  → sort(result.begin(), result.end(), compare);

  compare 함수

  bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  }