하루 하루는 성실하게
인생 전체는 되는대로

[프로그래머스] 순위 검색

3 minute read

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

  • 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
  • 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
  • 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
  • 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

/* 이하 중략 */

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

  • info 배열의 크기는 1 이상 50,000 이하입니다.
  • info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 개발언어 직군 경력 소울푸드 점수 형식입니다.
  • query 배열의 크기는 1 이상 100,000 이하입니다.
  • query의 각 문자열은 [조건] X 형식입니다.

풀이

70분
{info 문자열 : 점수 벡터}의 구조의 맵을 선언하여 가능한 조합마다 점수를 모아두고 정렬한 뒤, 쿼리문을 순회하며 점수를 조회하는 방식으로 구현했다. 모든 선택사항에 대해 322*2 = 24밖에 되지 않으므로, 쿼리문마다 맵을 순회해도 되겠다고 판단했다. 풀이 방법을 25~30분 정도 고민했는데, 실제로 코드로 옮길 때 문자열 처리에서 실수가 많이 있었다. sstream 헤더파일을 사용하면 조금 더 깔끔하게 코드를 작성할 수 있을 것 같아 공부했다.

코드

// 01:01 ~ 02:10
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<string> info_v;
    map<vector<string>,vector<int>> m;
    for(string s : info){
        info_v.clear();
        int idx = 0;
        for(int i = 0; i < s.length(); ++i){
            if(s[i] == ' '){
                info_v.push_back(s.substr(idx,i - idx));
                idx = i + 1;
            }
            if(info_v.size() == 4){
                m[info_v].push_back(stoi(s.substr(idx, s.length() - 1 - i)));
                break;
            }
        }
    }
    
    for(auto iter = m.begin(); iter != m.end(); ++iter){
        sort(iter->second.begin(), iter->second.end());
    }
    
    vector<string> query_v;
    int score, cnt;

    for(string q : query){
        query_v.clear();
        
        int idx = 0;
        for(int i = 0; i < q.length(); ++i){
            if(q[i] == ' '){
                if(q.substr(idx,i - idx) != "and") query_v.push_back(q.substr(idx,i - idx));
                idx = i + 1;
            }
            if(query_v.size() == 4){
                score = stoi(q.substr(idx, q.length() - 1 - i));
                break;
            }
        }

        cnt = 0;
        for(auto iter = m.begin(); iter != m.end(); ++iter){
            for(int i =0; i < 4; ++i){
                if(iter->first[i] != query_v[i] && query_v[i] != "-") break;
                if(i == 3){
                    for(int j = iter->second.size() - 1; j >= 0; --j){
                        if(iter->second[j] < score) break;
                        ++cnt;
                    }
                }
            }
        }
        answer.push_back(cnt);
    }
    
    return answer;
}

sstream

stringstream을 사용해서 코드를 다시 작성해봤다.

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

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<string> info_v(4);
    map<vector<string>,vector<int>> m;
    string temp;
    int score, cnt;
    
    for(string s : info){
        stringstream ss(s);
        for(int i = 0;i < 4; ++i){
            ss >> info_v[i];
        }
        ss >> score;
        m[info_v].push_back(score);
    }
    
    for(auto iter = m.begin(); iter != m.end(); ++iter){
        sort(iter->second.begin(), iter->second.end());
    }

    for(string q : query){
        stringstream ss(q);
        for(int i =0; i <4; ++i){
            ss >> info_v[i];
            if(i == 3){
                ss >> score;
                break;
            }
            ss >> temp;
        }
        
        cnt = 0;
        for(auto iter = m.begin(); iter != m.end(); ++iter){
            for(int i =0; i < 4; ++i){
                if(iter->first[i] != info_v[i] && info_v[i] != "-") break;
                if(i == 3){
                    for(int j = iter->second.size() - 1; j >= 0; --j){
                        if(iter->second[j] < score) break;
                        ++cnt;
                    }
                }
            }
        }
        answer.push_back(cnt);
    }
    
    return answer;
}

그런데 다시 작성한 코드가 효율성 테스트의 마지막 케이스를 통과하지 못했다. sstream의 성능이 그다지 좋지 못하구나 라는 생각에 다시 원래 코드를 제출했는데, 처음에 통과했던 코드가 효율성 테스트를 2문제나 통과하지 못했다(!?!). 이게 무슨일인가 싶어 카카오 공식 해설을 찾아보았는데, 애초에 처음 작성한 나의 코드는 통과를 하면 안 되는 코드였다. 점수를 순차적으로 탐색하지 않고 lower_bound를 사용해야 한다고 설명되어있다.

lower_bound

if(i == 3){
    cnt += iter->second.end() - lower_bound(iter->second.begin(), iter->second.end(), score);
}

위와 같이 코드를 바꾸어 통과할 수 있었다. lower_bound와 upper_bound는 algorithm 헤더에 정의되어있으며, lower_bound는 인자로 전달된 값 이상의 값이 처음으로 나오는 위치를 반환해주고, upper_bound는 초과의 값이 처음으로 나오는 위치를 반환해준다. 그림으로 이해하기 쉽게 설명된 블로그가 있어 하단에 첨부한다. 처음에 통과하는 오류가 발생한게 신기하다.

참고문헌

https://jackpot53.tistory.com/33

You may also enjoy