[프로그래머스] 귤 고르기 c++ (풀이, 코드, 정렬의 중요성?)

문제 링크

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

프로그래머스

 

문제

문제 설명

 

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

 

코드 및 풀이 (착오과정 포함)

 

틀린 코드

/*

귤 중 k개를 골라 판매 서로 다른 종류의 수를 최소화

이것도 dp로하면 되지 않을까? 하는 생각

그냥 많은것을 순서대로 더하면 되지 않을까?

다 벡터에 추가를 한다. 근데 겹치는것에 대해서 이중벡터로 v[i][1]++을 함으로써 정리를 하고

그다음에 sort를 한다(역순으로)

그리고 k에서 가장 큰값부터 빼면서 진행을 하면 될듯 싶다.

*/

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b){

    return a[1] > b[1]; //두번째 원소 즉, 갯수를 위주로 정렬

}

int solution(int k, vector<int> tangerine) {

    int answer = 0;

   

    vector<vector<int>> v;

    v.push_back({tangerine[0],1});

   

    for(int i = 1; i < tangerine.size(); i++){

        int is_element = 0;

        for(int j = 0; j < v.size(); j++){

            if(tangerine[i] == v[j][0]){

                v[j][1]++;

                is_element = 1;

                break;

            }

        }

        if(is_element == 0){

            v.push_back({tangerine[i],1});

        }

    }

   

    sort(v.begin(),v.end(),compare);

    int i = 0;

    while (k > 0 && i < v.size()){

        k -= v[i][1];

        answer++;

        i++;

    }

   

    return answer;

}

너무 간단하게 반복문을 돌게 되면서 새로운것이 나오면 이중벡터의 두번째 원소에 대해서 ++을 진행해서 진행을 한다고 생각을 했습니다.

 

물론 이 방법에 대해서 틀리지는 않았지만 결과론적으로는 시간초과 2개가 났습니다.

고친 코드

/*

2개에서 시간초과를 한다.. 생각해보면 조금 억지가 아닌가 싶긴하다.

생각을 해보니 처음에 들어온 tangerine에 대해서 sort를 진행하고 그냥 ++을 하면 이 번거러운 과정을 수고하지 않을 수 있지 않나?!

바보다..

*/

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b){

    return a[1] > b[1]; //두번째 원소 즉, 갯수를 위주로 정렬

}

int solution(int k, vector<int> tangerine) {

    int answer = 0;

   

    vector<vector<int>> v;

    sort(tangerine.begin(),tangerine.end());

    v.push_back({tangerine[0],1}); // 정렬후 첫 원소 push_back index1부터 비교할 예정

   

    int before_num = tangerine[0];

    int v_index = 0;

    for(int i = 1; i < tangerine.size();i++){

        if(tangerine[i] != before_num){

            v.push_back({tangerine[i],1});

            before_num = tangerine[i];

            v_index++;

        }else{

            v[v_index][1]++;

        }

    }

   

    sort(v.begin(),v.end(),compare);

    int i = 0;

    while (k > 0 && i < v.size()){

        k -= v[i][1];

        answer++;

        i++;

    }

   

    return answer;

}

잠시 30초 정도 가만히 생각을 해보니 간단하게 정렬을 하고(tangerine에 대해서) 전값을 기억을 해뒀다가 달라진다면 push_back을 하면 하나의 틀린코드에서 보셨던 불필요한 반복문을 지워 줄 수가 있습니다!!!

 

그래서

1. tangerine에 대해서 정렬

2. 전값이 다르다면 vector<vector<int>> v에 대해서 push_back(달라진 tagerine의 값, 1)을 함으로써 시간을 확연하게 줄였습니다.

확연히 달라졌지만 솔직하게 이 코드도 마음에 들지는 않긴하네요.. 근데 뭐 일단 다 풀었으니 나중에 level3,4쯤에 갈때는 확실하고 빡세게 공부를 해봐야겠습니다 :)