[프로그래머스 level2] 순위 검색 (c++)

프로그래머스 level2 수준인 순위검색 문제이다.

효율성 검사가 있어서 그런가
체감상 level2보다 어렵게 느껴졌다.

다시한번 문자열에 약하다는 걸 느꼈고 덕분에 새로운 구현 방식도 알게되었다!!

1차시도

1. query를 띄어쓰기 단위로 끊어 벡터에 저장
2. info를 띄어쓰기 단위로 끊어 벡터에 저장
3. 해당 query를 모든 info를 돌면서 만족하는 info가 발생할때마다 카운트

-> 시간복잡도 O(N^2) 발생

#include <string>
#include <vector>
#include <string.h>
#include <iostream>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    for(int i=0; i<query.size(); i++)
    {
        char ch[query[i].size()];
        strcpy(ch, query[i].c_str());
        char *ptr = strtok(ch, " ");
        vector <string> v;
        v.clear();
        while(ptr != NULL)
        {
            v.push_back(string(ptr));
            ptr = strtok(NULL, " ");
        }
        
        int cnt = 0;
        for(int j=0; j<info.size(); j++)
        {
            char c[info[j].size()];
            strcpy(c, info[j].c_str());
            char *pt = strtok(c, " ");
            vector <string> i;
            i.clear();
            
            while(pt != NULL)
            {
                i.push_back(string(pt));
                pt = strtok(NULL, " ");
            }
            
            int l = 0;
            for(int k=0; k<i.size(); k++)
            {
                if(k==4 && stoi(i[k]) >= stoi(v[v.size()-1])) {
                    cnt++; 
                }
                else {
                    if(v[k*2]=="-") {continue;}
                    if(i[k] == v[k*2]) continue;
                    else break;
                }
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

이렇게 했는데 segmentation fault가 겁나 많이 떠버림..
이 방법을 고쳐볼까 했지만 어차피 효율성이 꽝일거라 예상 되어서 다른 방법을 찾았다.

2차시도

효율성을 줄이기 위해서는 score 정렬이 필요하다고 생각되었다.
이것외에는 방법이 떠오르지 않아 구글링을 하였다.

참고코드

구현

1. info 파싱
   -를 포함한 모든 경우의 수 map에 넣어주기
2. 이분탐색을 위해 score 기준으로 각각의 map 정렬
3. query 파싱
   띄어쓰기를 제외한 문자열을 모두 합해줌
4. query 문자열로 info map에서 조건의 만족하는 경우의 수를 찾음
   lower_bound() 사용

코드

#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>

using namespace std;
unordered_map <string,vector<int>> um;

void addCases(string *s, int score)
{
    for(int i=0; i<16; i++)
    {
        string str="";
        int num = i;
        for(int j=3; j>=0; j--)
        {
            if(num <= 0 || num%2 == 0)
            {
                str = "-" + str;
            }
            else str = s[j] + str;
            num /= 2;
        }
        um[str].push_back(score);
    }
}
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    string s[4], str="";
    
    for(int i=0; i<info.size(); i++)
    {
        istringstream stt(info[i]);
        stt >> s[0] >> s[1] >> s[2] >> s[3] >> str;
        addCases(s, (int)stoi(str));
    }
    
    for(auto itr = um.begin(); itr!=um.end(); itr++)
    {
        sort(itr->second.begin(), itr->second.end());
    }
    
    for(int i=0; i<query.size(); i++)
    {
        istringstream stt(query[i]);
        stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3] >> str;
        int score = (int)stoi(str);
        
        vector <int> v = um[s[0]+s[1]+s[2]+s[3]];
        if(v.size()!=0)
        {
            int idx = lower_bound(v.begin(), v.end(), score) - v.begin();
            answer.push_back(v.size() - idx);
        }
        else answer.push_back(0);
    }
    return answer;
}

C++ 문법

1. 문자열 나누기

크게 두가지 방식으로 나눌 수 있다.
문자열 나누는 2가지 방법

이 중 나는 무조건 istringstream 방식을 사용하기로 했다.
(예외 : 문자열 구분자 2개 이상이면 strtok 사용)

istringstream 사용 방법

위의 블로그에서도 알 수 있듯이 stringstream은 공백과 '\n'을 제외하고 문자열에서 맞는 자료형의 정보를 빼낸다.
따라서 다음과 같이 아주 간편하게 문자열을 분리할 수 있다.
꼭 기억해놔야하는 문법이다.

istringstream stt(query[i]);
stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3] >> str;

2. map 사용법

카카오 문제를 풀기 전까지는 Map을 그다지 많이 사용하지 않았는데 이제는 거의 매번 사용하는 것 같다.

unordered_map <string,vector<int>> um;
vector <int> v = um[s[0]+s[1]+s[2]+s[3]];

이번에 알게된 방법 (위 코드 참고)

1) 동일한 string에 대해 int값을 여러개 삽입하는데 아주 유용하다.
2) 값이 아주 많거나 효율적으로 사용해야하는 경우 unordered_map을 사용할 수 있다.
unordered_map 사용법
3) map의 second 자료형이 vector인 경우에 vector에 할당가능 (이건 당연한 소리임. 근데 이걸 여지껏 안 이용했다는게 좀 충격)

그러면 왜 unordered_map이 효율적인가?

unordered_map은 해쉬테이블로 구현한 자료구조로 탐색시간복잡도는 O(1)이 된다.
반면 map은 Binary Search Tree로 탐색 시간 복잡도는 O(logn n)이다.
따라서 unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을시 월등히 좋은 성능을 보인다.
하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수 있다.