[프로그래머스/C++] 알고리즘 - 순위 검색

안녕하세요! 테크지니어22입니다.

오늘은 프로그래머스 알고리즘 - 순위 검색을 풀어보도록 하겠습니다.

Level2인데 제가 느끼기에 어렵네요. c++이어서 문자열이 더 어렵게 느껴지기도 하네여.

 

 

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

프로그래머스

 

[문제 접근]

시간 제한은 정확히 나와 있지 않으나 query가 10만이하이고 info 크기가 5만이하이기 때문에 둘을 곱하면 50억의 연산이 필요합니다.
즉, 이중 for문을 사용하면 효율성에서 통과가 안될 거 같은 냄새를 풍기고 있습니다. 그러나 이중 for문 말고 방법이 사실 떠오르지 않아 

희망을 가지고 이중for문을 구현했으나 역시 효율성에서 통과를 하지 못했습니다.

이후 다른 풀이들을 참고했는데, 이분탐색, 해쉬맵, 비트마스킹 등을 이용했습니다. 그러나 결국 핵심은 이중 for문을 하나의 for문으로 바꾸어 시간복잡도를 O(N^2)에서 O(N)이나 O(NlogN)으로 바꾸는 것입니다.

 

[풀이 전략]

그러기 위해서는 완전탐색하면서 세는 게 아니라 미리 자료구조에 저장을 해서 query를 하나씩 검사할 때 저장한 자료구조를 바로 이용해서 개수를 세어야 합니다. query에 '-'도 존재를 고려했을때  코테 점수를 제외하고 (3+1) x(2+1) x (2+1) x (2+1) = 108의 경우의 수가 나옵니다. 각 경우를 키로 사용하고 값은 코테 점수를 가지는 unordered_map을 생성하고 구성했습니다.

이 때 모든 경우를 고려하기 위해서 비트마스킹을 이용했습니다.

 

+ c++을 split함수가 없기 때문에 직접 구현을 해주어야합니다 ㅠㅠ. 저 코드는 바킹독님이 작성하신 코드인데 직관적이어서 두고두고 외워서 쓰려고요

 

[코드]

이중 for문 풀이 - 효율성 실패 

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;


vector<string> split(string& s, string& sep){
    vector<string> ret ;
    int pos = 0;
    while(pos <s.size()){
        int nxt_pos = s.find(sep,pos); // find의 두번쨰 인자는 찾기 시작하는 주소값
        if(nxt_pos == -1) nxt_pos = s.size();
        if(nxt_pos - pos > 0) ret.push_back(s.substr(pos, nxt_pos - pos));
        pos = nxt_pos + sep.size();
    }
    return ret ; 
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    multiset<pair<int,vector<string>>> mset ; 
    
      for(auto pe : info) {
          string sep =" ";
            vector<string> person = split(pe, sep);
            int score = stoi(person.back()); person.pop_back();
            mset.insert({score, person});
      }
        
    for(auto q: query) {
        int cnt = 0 ;
        string sep = " and ";
        vector<string> p = split(q, sep);
        string tmp = p.back(); p.pop_back();
        sep = " ";
        vector<string> temp = split(tmp,sep); 
        p.push_back(temp[0]);
        int score = stoi(temp[1]);
        
        auto it = mset.lower_bound({score,{}});
        for(auto ite = it ; ite != mset.end(); ite++) {
             bool flag = true ;
            for(int i = 0 ; i < p.size() ; i++){
                if(p[i] == "-") continue;
                
                if((*ite).second[i] != p[i]) {flag = false ; break;} 
            }
            
            if(flag) cnt++;
        }
        answer.push_back(cnt);
    }
    return answer;
}

 

성공 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;


vector<string> split(string& s, string& sep){
    vector<string> ret ;
    int pos = 0;
    while(pos <s.size()){
        int nxt_pos = s.find(sep,pos); // find의 두번쨰 인자는 찾기 시작하는 주소값
        if(nxt_pos == -1) nxt_pos = s.size();
        if(nxt_pos - pos > 0) ret.push_back(s.substr(pos, nxt_pos - pos));
        pos = nxt_pos + sep.size();
    }
    return ret ; 
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    unordered_map<string,vector<int>> m ; 
    
      for(auto pe : info) {
          string sep =" ";
            vector<string> person = split(pe, sep);
            int score = stoi(person.back()); person.pop_back();
          
          for(int i = 0 ; i < 16 ; i++){
            string tmp ; 
              for(int j = 0 ; j < 4 ; j++){
                  tmp += (i & (1 << j)) ? person[j] : "-";
              }
              m[tmp].push_back(score);
          }
      }
    
    for(auto &iter: m) sort(iter.second.begin(), iter.second.end()); 
        
    for(auto q: query) {
        int cnt = 0 ;
        string sep = " and ";
        vector<string> p = split(q, sep);
        string tmp = p.back(); p.pop_back();
        sep = " ";
        vector<string> temp = split(tmp,sep); 
        p.push_back(temp[0]);
        int score = stoi(temp[1]);
        
        string str = p[0]+p[1]+p[2]+p[3];
        
        cnt += m[str].end()- lower_bound(m[str].begin(),m[str].end(),score);
        
        
        answer.push_back(cnt);
    }
    return answer;
}

 

[배울 점]

- 문자열 split 커스텀 함수 작성법 숙지하기

- 시간복잡도를 줄이려면 이분탐색, 이진트리검색, 해쉬맵 고려하기.