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

문제 내용

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

문제의 유형 및 풀이 방법

효율성 테스트도 있어, map 자료구조와 이분 탐색(Binary search)을 활용해야 하는 문제이다.

먼저 info 배열의 각 원소로부터 만들 수있는 모든 경우의 infoString을 key로 한 map을 만든다. key의 value는 점수를 저장할 벡터이다.

이렇게 map에다가 모든 경우의 infoString 및 score를 넣게되면, java - - pizza 150 같은 query가 들어와도 map에서 이를 찾아서 결과를 구할 수 있다.

// info로부터 만들 수 있는 모든 경우의 infoString을
// map{infoString: vec{score1, score2, score3, ...}} 에다가 넣어준다.
// e.g.
// info: java backend junior pizza 150 이라면, 총 16(2^4)개의 key가 map에 추가된다.
// javabackendjuniorpizza: {150}
// javabackendjunior-: {150}
// ... 중략 ...
// ----: {150}
// 이후에 java - - pizza 100이 들어온다면, 이는 이미 map에 추가된 상태이므로
// 점수 100이 추가되어, java--pizza: {150, 100} 이렇게 처리된다.
void InsertInfoIntoMap(const vector<string>& infoList, map<string, vector<int>>& infoMap)
{
    int score = 0;
    istringstream iss;
    string infoString[4][2] = {
        {"-"},
        {"-"},
        {"-"},
        {"-"}
    };
    string keyString = "";

    for (string info : infoList)
    {
        // info 문자열 파싱
        iss.clear();
        iss.str(info);
        iss >> infoString[0][1] >> infoString[1][1] >> infoString[2][1] >> infoString[3][1] >> score;

        // 모든 경우의 info를 만들어 map에 삽입
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                for(int k = 0; k < 2; k++)
                {
                    for(int l = 0; l < 2; l++)
                    {
                        keyString = infoString[0][i] + infoString[1][j] + infoString[2][k] + infoString[3][l];
                        vector<int> scores;
                        infoMap.insert(make_pair(keyString, scores));
                        infoMap[keyString].push_back(score);
                    }
                }
            }
        }
    }
}

infoMap 을 만들었으면, query를 파싱하여 keyString을 만들고, 정렬된 상태에서의 이분 탐색(lower_bound 함수 사용)으로 query에 해당하는 결과를 얻는다.

int GetResultFromInfoMap(string query, const map<string, vector<int>>& infoMap)
{
    istringstream iss(query);
    string language = "";
    string jobGroup = "";
    string career = "";
    string soulFood = "";
    int score = 0;
    string temp = "";
    string keyString = "";
    int answer = 0;

    // query를 파싱하여 keyString 만들기
    iss >> language >> temp >> jobGroup >> temp >> career >> temp >> soulFood >> score;
    keyString = language + jobGroup + career + soulFood;

    // keyString에 해당하는 scores가 없으면 0 리턴
    auto mapIter = infoMap.find(keyString);
    if (infoMap.end() == mapIter)
    {
        answer = 0;
    }
    else
    {
        const vector<int>& scores = mapIter->second;
        // score 이상 받은 지원자의 수
        answer = scores.end() - lower_bound(scores.begin(), scores.end(), score);
    }

    return answer;
}

복습해야할 내용

• <sstream>의 istringstream 클래스 활용법. 파싱을 간단하게 구현할 수 있다.
  istringstream은 공백 및 \n을 구분자로 파싱하기 때문에, 다른 문자로 파싱하려면 getline 함수를 사용해야 한다.

#include <sstream>
#include <string>
#include <iostream>

using namespace std;


int main()
{
	string text = "Hello, my name is John.";
	istringstream iss;
	string stringArray[5];
	iss.str(text);
	
	// 파싱 방법 1. >> operator 사용
	iss >> stringArray[0] >> stringArray[1] >> stringArray[2] >> stringArray[3] >> stringArray[4];
	for (string s : stringArray)
	{
		cout << s << endl;
	}
	/*
	결과:
	Hello,
	my
	name
	is
	John.
	*/
	
	// 파싱 방법 2. while문 사용
	string token = "";
	iss.clear(); // iss 재사용 시에는 리셋(clear 함수) 필수
	iss.str(text);
	while (iss >> token)
	{
		cout << token << endl;
	}
	/*
	결과:
	Hello,
	my
	name
	is
	John.
	*/
	
	// 파싱 방법 3. getline 함수 사용
	iss.clear();
	iss.str(text);
	while(getline(iss, token, 'e'))
	{
		cout << token << endl;
	}
	/*
	결과:
	H
	llo, my nam
	is John.
	*/
}

• <algorithm>의 lower_bound, upper_bound 함수 사용법주의할 점: 원소가 정렬되어 있어야 함.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


int main()
{
	vector<int> vec = { 3, 1, 4, 2, 4 };
	sort(vec.begin(), vec.end());  // -> {1, 2, 3, 4, 4}

	// 4가 첫 번째로 등장하는 인덱스 구하기
	cout << lower_bound(vec.begin(), vec.end(), 4) - vec.begin() << endl;
	// 결과: 3

	// 4가 마지막으로 등장하는 인덱스 구하기
	// upper_bound는 lower_bound와는 다르게 조건을 만족하는 인덱스+1 인 iterator를 리턴하는 것에 주의.
	// 즉 4가 인덱스 4에서 마지막으로 등장했다면 인덱스 5를 리턴한다.
	cout << upper_bound(vec.begin(), vec.end(), 4) - vec.begin() - 1 << endl;
	// 결과: 4
}

소스 코드

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

using namespace std;

#define IDX_LANGUAGE 0
#define IDX_JOBGROUP 1
#define IDX_CAREER 2
#define IDX_SOULFOOD 3
void InsertInfoIntoMap(const vector<string>& infoList, map<string, vector<int>>& infoMapOut)
{
    istringstream iss;
    string infoString[4][2] = {
        {"-"},
        {"-"},
        {"-"},
        {"-"}
    };
    int score = 0;
    string keyString = "";

    for (string info : infoList)
    {
        iss.clear();
        iss.str(info);
        iss >> infoString[IDX_LANGUAGE][1] >> infoString[IDX_JOBGROUP][1] >>
            infoString[IDX_CAREER][1] >> infoString[IDX_SOULFOOD][1] >> score;

        for(int i = 0; i < 2; i ++)
        {
            for (int j = 0; j < 2; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    for (int l = 0 ; l < 2; l++)
                    {
                        keyString = 
                            infoString[IDX_LANGUAGE][i] + 
                            infoString[IDX_JOBGROUP][j] + 
                            infoString[IDX_CAREER][k] +
                            infoString[IDX_SOULFOOD][l];
                        vector<int> scores;
                        // 이미 존재하는 key이면 insert해도 추가가 안됨.
                        infoMapOut.insert(make_pair(keyString, scores));
                        infoMapOut[keyString].push_back(score);
                    }
                }
            }
        }
    }
}

int GetResultFromInfoMap(string query, const map<string, vector<int>>& infoMap)
{
    istringstream iss(query);
    string language = "";
    string jobGroup = "";
    string career = "";
    string soulFood = "";
    int score = 0;
    string temp = "";
    string keyString = "";
    int answer = 0;

    // query를 파싱하여 keyString 만들기
    iss >> language >> temp >> jobGroup >> temp >> career >> temp >> soulFood >> score;
    keyString = language + jobGroup + career + soulFood;

    // keyString에 해당하는 scores가 없으면 0 리턴
    auto mapIter = infoMap.find(keyString);
    if (infoMap.end() == mapIter)
    {
        answer = 0;
    }
    else
    {
        const vector<int>& scores = mapIter->second;
        // score 이상 받은 지원자의 수
        answer = scores.end() - lower_bound(scores.begin(), scores.end(), score);
    }

    return answer;
}

vector<int> solution(vector<string> infoList, vector<string> queries)
{
    vector<int> answer;
    map<string, vector<int>> infoMap;

    InsertInfoIntoMap(infoList, infoMap);

    // infoMap의 value인 점수 벡터를 오름차순 정렬
    // 정렬을 해야 std::lower_bound 함수 사용 가능.
    for (auto& item : infoMap)
    {
        sort(item.second.begin(), item.second.end());

    }

    // query에 해당하는 답을 구하기
    for (auto& query : queries)
    {
        answer.push_back(GetResultFromInfoMap(query, infoMap));
    }

    return answer;
}