풀이 소요시간 : 매우 많이..(실패)

최근 풀이한 문제중 가장 나를 힘들게했다. 문자열 파싱정도는 평소에 익혀뒀던지라 20분이 안되는 시간에 구현을 마치고 정답을 제출했는데, 정확성 테스트는 만점을 받았지만 효율성 테스트에서 0점을 받아 통과하지 못했다.

딱봐도 그냥 문자열 구현 문제인데 시간복잡도를 고려할 요소가 있나 싶어서 고민을 하다가 결국 방법이 생각이 나지 않아 풀이를 참고했는데, 문자열 파싱 말고도 생각보다 굉장히 많은 요소를 요구하는 문제였다.

Unordered_map 의 사용과 vector 요소를 가진 map 의 사용

일단 나는 map 속에 vector 요소가 포함된 자료구조를 사용해본 경험이 없었다. 이 문제에서는 info 자료를 순회 및 파싱하면서 이미 map 에 가능한 모든 경우의 수를 따져서 vector 에다가 지원자의 점수를 모두 입력해둬야 했다. 또한 key 값의 정렬이 꼭 필요한 것이 아닌 이상 map 보다는 unordered_map 의 사용을 생활화 해야겠다는 생각이 들었다.

map 자료구조는 유사 이진트리 형태로 O(nlog(n)) 의 시간복잡도를 가지지만
unordered_map 자료구조는 해시 테이블 형태로 O(1) 의 아주 빠른 복잡도를 가진다.

lower_bound(v.begin(), v.end(), score) 함수의 사용

탐색 시간을 줄이기 위해 사용되어야 한다. 이 함수같은 경우 반환값이 iterator 자료형이다.
따라서 정수형 인덱스 값을 얻고싶다면 lower_bound(v.begin(), v.end(), score) - v.begin() 처럼 v.begin() 값을 빼주어야한다.

score 값 이상의 원소 갯수를 알고싶은 경우 v.size() - lower_bound(...) - v.begin() 을 연산해주면 되겠다.

map 값을 수정하려면 iterater 나 참조표기 &를 사용

평소 map 의 구성요소를 사용할 때 처럼

for(auto E : Map) 
{
	sort(E.second.begin(), E.second.end());
}

코드를 짰더니 정렬이 제대로 되지 않아 결과값이 이상하게 나왔다.
이유가 뭔가 하고 찾아봤더니 sort 함수에 복사본이 전달되어 원본 값이 안바뀐다는 것이였다.

전에 구조체 값을 변경할 때도 기본적인 문법을 몰라서 시간을 낭비했는데 이번에도 마찬가지다.
반드시 기억하도록 해야겠다.

전체 코드

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

//지원자 정보 저장
unordered_map<string, vector<int>> Map;
vector<string> Temp;


vector<int> solution(vector<string> info, vector<string> query) {
    
    vector<int> Ans;
    
    for(string str : info)
    {
        stringstream ss(str);
        string token;
        while(getline(ss, token, ' '))
        {
            Temp.push_back(token);
        }
        
        string st[2] = { Temp[0], "-"};
        string st2[2] = { Temp[1], "-"};
        string st3[2] = { Temp[2], "-"};
        string st4[2] = { Temp[3], "-"};
        // 2*2*2*2 = 16가지 모든 경우의 수
        
        for(int i1 = 0; i1 < 2; i1++)
            for(int i2 = 0; i2 < 2; i2++)
                for(int i3 = 0; i3 < 2; i3++)
                    for(int i4 = 0; i4 < 2; i4++)
                        Map[st[i1]+st2[i2]+st3[i3]+st4[i4]].push_back(stoi(Temp[4]));
        
        //초기화
        Temp.clear();
    }
    
    
    //벡터 정렬
    for(auto it = Map.begin(); it != Map.end(); it++)
    {
        sort(it->second.begin(), it->second.end());
    }
    
    
    for(string str : query)
    {
        stringstream ss(str);
        string token;
        while(getline(ss, token, ' '))
        {
            Temp.push_back(token);
        }
        
        int test = stoi(Temp[7]);
        vector<int> V = Map[Temp[0]+Temp[2]+Temp[4]+Temp[6]];

        int Data = V.size() - (lower_bound(V.begin(), V.end(), test) - V.begin());
        Ans.push_back(Data);
        Temp.clear();
    }
    
    
    return Ans;
}