[Today]

• 알고리즘코드카타
• 팀프로젝트 - 닷지게임

[개발일지]

• 알고리즘코드카타 - 프로그래머스_귤고르기

처음 내가 작성한 코드

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 1;
    vector<pair<int, int>> pv;
    map<int, int> m;
    for(int i : tangerine) m[i]++;
    for(auto it : m){
        pv.push_back(make_pair(it.second, it.first));
    }
    sort(pv.rbegin(), pv.rend());
    int temp = 0;
    for(int i = 0; i < pv.size(); i++){
        temp += pv[i].first;
        if(temp < k) answer++;
    }

    return answer;
}

→ map과 pair를 오랜만에 사용해서 적절히 검색하여 문제를 풀었다.

다만 조금 쓸데없는 구현을 한 것 같아서 찝찝했다. 예를 들어 vector에 pv[i].second는 결국에는 필요 없는 정보였다. 다른 방법이 있을 것 같았다.

리팩토링한 코드

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    int m = *max_element(tangerine.begin(), tangerine.end());
    vector<int> v(m + 1, 0);
    for(int t : tangerine){
        v[t]++;
    }
    sort(v.rbegin(), v.rend());
    int temp = 0;
    for(int i = 0 ; i < v.size() ; i++){
        answer++;
        temp += v[i];
        if(temp >= k) return answer;
    }
    return answer;

→ 이렇게 하면 map과 pair 모두 안써도 되고, vector 로만 구현할 수 있다.

우선 *max_element로 크기가 최대인 귤의 크기를 구한후 그만큼 개수의 +1의 0으로 이루어진 벡터를 선언한다.

ex) 크기가 5인 귤이 있으면 [0, 0, 0, 0, 0, 0]을 선언하는 것이다. 그리고 크기가 1인 귤이 입력되면 1번째 인덱스의 값이 1증가 크기가5인 귤이 입력되면 5번째 인덱스의 값이 1증가 그래서 만약 [1, 3, 2, 5, 4, 5, 2, 3] 이 입력된다면 벡터에는 [0, 1, 2, 2, 1, 2] 이런식으로 입력이 될것이다.

그리고 내림차순으로 정렬한다면 [2, 2, 2, 1, 1, 0] 이런식으로 정렬이되고 이렇게 정렬이 됐다면 나머지는 식은죽먹기

<aside> 💡 기억해야하는 포인트 *1. max_element(tangerine.begin(), tangerine.end()); ⇒ 최대값을 구해준다. 2. vector<int> v(m + 1, 0); ⇒ m+1개의 0으로 이루어진 벡터를 선언과 동시에 초기화해준다. 3. sort(v.rbegin(), v.rend()); ⇒ 내림차순 정렬

</aside>