[2021 Kakao blind recruitment] 순위검색

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

코딩테스트 연습 - 순위 검색

이 문제는 처음에는 문자열을 하나씩 리스트에 담아서 이중포문으로 각 문장들을 비교하는 방법으로 풀었었다.

그러니까 정확성은 통과하는데 효율성은 통과하지 못했다.

 

통과할 수 있는 방법은 unordered map 을 사용하는 방법

그리고 빠른 탐색방법인 low_bound(v.begin(), v.end(), target) 에 대해 정리하고자 한다!

또한, 다른 사람의 코드를 참고하여 알게 된 istringsteam 사용법에 대해 정리하고자 한다.

 

low_bound()

low_bound는 이진탐색으로 원소를 탐색하는 함수이다.

이진탐색이므로 초기에 sort 가 되어있는 벡터가 필요하다.

4 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 리턴

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

int main() {
 vector <int> v = {1, 2, 3, 9, 10, 0, 5};
 sort(v.begin(), v.end());

 vector <int>::iterator it = lower_bound(v.begin(), v.end(), 4);
 cout << *it << " idx: " << it - v.begin() <<endl;
}

 

istringstream()

string 을 split 하는데 유용하게 사용할 수 있는 함수이다.

 #include <iostream>
 #include <cstring>
 #include <sstream>
 #include <algorithm>
 using namespace std;
 int main() {
     string str = "java and python and cpp and ruby";
     string s[7];

     istringstream stt(str);
     stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3];
     cout << s[0] << s[1] << s[2] << s[3] <<endl;
     // javapythoncppruby
 }

 #include <iostream>
 #include <cstring>
 #include <sstream>
 #include <algorithm>
 using namespace std;
 int main() {
     string str = "java python cpp ruby";
     string s[7];

     istringstream stt(str);
     stt >> s[0] >> s[1] >> s[2] >> s[3];
     cout << s[0] << s[1] << s[2] << s[3] <<endl;
     // javapythoncppruby
 }

unordered_map

map 보다 빠른 탐색을 할 수 있습니다.

unordered_map 은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1) 입니다.

map 은 Binary Search Tree 로 구현한 걸로 O(logN) 의 복잡도를 갖습니다.

헤더는 #include <unoredered_map> 입니다.

#include <unordered_map>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

unordered_map <string, int> um;

int main() {

	if(um.empty()) printf("this is empty\n");

	um.insert(make_pair("key", 1));
	um["kakao"] = 2;
	um.insert({"melon", 3});

	printf("size : %lu\n", um.size());

	for(auto ele: um) {
		printf("key: %s, value: %d\n", ele.first.c_str(), ele.second);
	}

	if(um.find("kakao") != um.end()) {
		um.erase("kakao");
	}
	printf("size : %lu\n", um.size());

	for(auto ele: um) {
		printf("key: %s, value: %d\n", ele.first.c_str(), ele.second);
	}

	return 0;
}

 

[풀이방법]

1. info 문자열들을 split 하고 여러가지 경우를 생성한다.

java backend junior pizza 150

가 들어왔다고 하면

STRING                           SCORE

javabackendjuniorpizza = 150

 

-backendjuniorpizza = 150

java-juniorpizza = 150

javabackend-pizza = 150

javabackendpizza- = 150

 

--juniorpizza = 150

java--pizza = 150

javabackend-- = 150

 

java--- = 150

---pizza = 150

 

----- = 150

 

이런식으로 저장한다.

 

2. 점수 기준으로 sort 해준다.

모든 문장을 이런식으로 바꿔서 저장한 후, 각 문장들에 Score 들이 쌓일 건데 쌓인 score 들을 sort 해준다. (binary search 를 위해)

for(auto it=scores.begin(); it != scores.end(); it++)

       score(it->second.begin(), it->second.end());

 

3. query 문자열들을 " and " 와 " " 로 split 해서 압축한다.

"java and backend and junior and pizza 100"

javabackendjuniorpizza 로 문자열이 압축이 된다.

4. 검색한다.

vector <int> v = scores["javabackendjuniorpizza"] 중에 100 이하인 원소들을 검색한다.

여기서 lower_bound 를 사용

it = lower_bound(v.begin(), v.end() , 100);

v.size() - (it - v.begin())  이 100 이상인 원소의 갯수

 

 

[코드]

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

unordered_map <string, vector <int>> scores;

void addCases(string *s, int score) {
    for(int i=0; i<16; i++) {
        string str = "";
        int a = i;
        for(int j=3; j>=0; j--) {
            if(a <=0 || a%2 == 0) str = '-' + str;
            else str = s[j] + str;
            a/=2;
        }
        scores[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 it=scores.begin(); it!=scores.end(); it++)
        sort(it->second.begin(), it->second.end());


    for(int i=0; i<query.size(); i++) {
        int score;
        istringstream stt(query[i]);
        stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3] >> str;
        score = stoi(str);

        vector <int> v = scores[s[0]+s[1]+s[2]+s[3]];
        if(v.size() != 0) {
            auto it = lower_bound(v.begin(), v.end(), score);
            answer.push_back(v.size()-(it-v.begin()));
        }
        else
            answer.push_back(0);
    }

    return answer;

}