Lv 0. 등수 매기기 *다시 풀어보기*

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

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<vector<int>> score) {
    vector<int> answer;
    vector<int> tmp;
    vector<int> mid;
    for(auto t: score){
        tmp.push_back((t[0]+t[1])); //int로 딱 떨어지게 제시해준다는 내용이 없어서 /2 를 해버리면 소수점 이하가 잘리니까 안된다.
        mid.push_back((t[0]+t[1]));
    }
    pair<int,int> a[15]={};
    sort(tmp.begin(),tmp.end(),greater<>());
    for(int i=0; i<tmp.size();i++){
        if(i!=0 && (tmp[i]==a[i-1].second)) {
            a[i]={a[i-1].first,tmp[i]};     
        }
        else a[i]={i+1,tmp[i]};
    }
    for(auto c: mid){
        for(int i=0; i<mid.size();i++){
            if(c==a[i].second){
                answer.push_back(a[i].first);               
                break;
            }    
        }
    }
    return answer;
}

처음 생각이 난 방향으로 함수를 만들어서 위와 같이 만들어서 제출하였고, 이때에 처음에는 (t[0]+t[1])/2 의 값을 기준으로 잡았었는데, 

제출하고보니 틀린 케이스가 나오는걸 보고, 문제를 다시 읽어봐도 이 값이 꼭 2로 나누었을때 평균이 int로 나온다 라는 얘기가 없어서, 해당 케이스에서의 예제로 생각되는건, /2 를 하면서 소수점 이하 부분이 버려지면서 차이가 나야할 부분이 나지 않는 형태가 아닌가 싶어서 

t[0]+t[1] 의 값을 기준으로 비교하는 형태로 함수를 작성했다. 

 

일단 굉장히 비효율적인 형태로 작성한것 같다는 생각이 들어서 조금 아쉬운데 가장 처음에 생각난 형태가 위와 같고, 문제에서 시간복잡도와 공간복잡도에 대한 제약이 없어서 위와같이 만들었다. 

 

다른 사람의 풀이를 통해서 조금 더 효율적인 풀이들을 접하게 되었는데, 보고 배울만한 풀이들을 첨부해보겠다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<vector<int>> score) {
    vector<int> answer;
    for(auto& s : score){
        s.emplace_back(s[0] + s[1]);
    }
    
    for(const auto v : score){
        int count = 0;
        for(const auto t : score){
            count += (t[2] > v[2]);
        }
        answer.emplace_back(count + 1);
    }
    return answer;
}

가장 처음에 많은 추천을 받아 탑으로 올라와있는 코드의 경우 위와 같은데,  이 코드의 경우는 따지고 보면 내가 작성한 코드와 매우 유사한 로직을 가지고 있는 코드이다. 결국 더 간결해 보이는 이유는, 새로운 vector를 선언하는 것이 아니라, 기존에 주어지는 score 벡터의 원소에 해당하는 vector에 두 원소의 합 원소를 추가적으로 넣어서, 그 원소들을 가지고 서로 비교하는 형태이기 때문에 선언하는 부분이 없어서 짧고, 그리고 핵심 부분은 결국 그 부분들을 서로 비교하는 이중 for문을 통해서 그것보다 더 큰것이 참인지 아닌지의 형태로 더 큰 것들의 갯수들을 더하면서 그게 몇번째에 해당하는 형태인지 찾아내는 방식으로 구현한 것이다. 

 

로직은 비슷하지만, 코드가 아주 짧고 간결해서 마음에 든다. 

 

다른 풀이로는, 처음에 자료구조를 통해서 문제를 해결할 수 있지 않을까 싶었는데, 그와 같은 방법을 사용하는 풀이를 첨부해보겠다. 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;

vector<int> solution(vector<vector<int>> score) {
    map<int, int> m;
    vector<int>ans(score.size());
    for(auto i: score)m[i[0]+i[1]]++;
    stack<pair<int,int>> s;
    for(auto i: m){
        s.push(make_pair(i.first,i.second));
    }
    int r=1;
    while(s.size()){
        pair<int,int> p = s.top();
        s.pop();
        for(int i=0; i<score.size(); i++){
            if(p.first==score[i][0]+score[i][1])ans[i]=r;
        }
        r+=p.second;
    }

    return ans;
}

map 을 사용한 형태의 코드로, map을 통해 정렬되고 우선순위가 존재하는 형태로 자료가 쌓이므로 그것을 이용하는 풀이이다. 

map에 대한 이해가 수반되어야 위와 같이 생각해낼 수 있을 것이다. 

 

 

  Comments,     Trackbacks