[ 프로그래머스 순위 검색 (Lv2) ] (C++)

프로그래머스의 순위검색(Lv2) 문제이다.

 

[ 문제풀이 ]

문제에서 지원자들의 정보와 희망하는 지원자들의 정보가 주어졌을 때, 희망하는 지원자들에 부합하는 지원자들이 각각 몇명이 있는지 구해야 하는 문제이다.

주어진 지원자들의 정보부터 시작해서 정답을 도출하는 것 까지 단계별로 나눠서 이야기해보자.

 

#1. 지원자들의 정보 관리

먼저, 지원자들은 총 5가지의 정보를 가지고 있다.

[ 개발언어 / 직군 / 경력 / 소울푸드 / 코딩테스트 점수 ] 이렇게 총 5가지의 정보를 가지고 있다.

그럼 이 5가지의 정보들을 각각 어떻게 관리했는지 구체적으로 알아보자.

 

Info - 1) 개발언어

개발언어는 총 3가지가 있다. [ cpp , java , python ] 3가지 언어가 있는데 본인은 이 언어들을 각각 숫자 1, 2, 3 으로

매핑을 해 주었다. 즉, cpp = 1번, java = 2번 , python = 3번 으로 매핑을 시켜 주었다.

왜 이렇게 숫자로 바꿔서 매핑을 시켜주었을까 ?? 이 부분에 대한 이야기는 나머지 정보들도 모두 알아본 후에 마지막에 하도록 하자.

무튼 이렇게 숫자로 바꿔서 매핑을 시켜 주었다. 판단하는 방법은 굉장히 간단하다.

각 언어들이 문자열로 주어지는데, 문자열의 첫 번째 글자, 즉, "cpp" 라는 문자열에서 'c', "java"라는 문자열에서 'j',

"python"이라는 문자열에서 'p' 라는 문자가 모두 각각 다르기 때문에 이 가장 앞에 문자들만을 통해서 숫자로 매핑시키는 과정을 진행해 주었다.

그렇다면, 우리가 "개발언어"를 통해서 얻을 수 있는 값은 1, 2, 3 3개가 있을 것이다. 이 외에 다른 숫자를 개발언어로 가진 지원자는 존재하지 않을 것이다.

 

Info - 2) 직군

직군은 총 2가지가 있다. [ backend , frontend ] 2가지가 있는데, 이 또한 마찬가지로 숫자 1 , 2 로 매핑을 시켜 주었다.

개발언어와 마찬가지로, 주어진 문자열의 가장 첫 글자인 'b' 와 'f'를 통해서 매핑된 숫자를 쉽게 찾을 수 있을 것이다.

본인은 "backend"는 '1'로 "frontend"는 '2'로 매핑을 시켜 주었다.

그렇다면, 우리가 "직군"을 통해서 얻을 수 있는 값은 1, 2 총 2개가 있을 것이다. 이 외에 다른 숫자를 직군으로 가지는 지원자는 존재하지 않을 것이다.

 

Info - 3 , 4) 경력 & 소울푸드

개발언어와 직군과 똑같다.

경력에는 [ junior , senior ] 2가지가 있는데, 이 또한 마찬가지로 1, 2로 매핑을 시켜 주었다.

소울푸드에는 [ chicken , pizza ] 2가지가 있는데, 이 또한 마찬가지로 1, 2로 매핑을 시켜 주었다.

 

Info - 5) 코딩테스트 점수

마지막으로 코딩테스트 점수이다. 코딩테스트 점수는 어떻게 매핑을 시켜 주어야 할까 ???

본인은 코딩테스트 점수는 매핑을 시켜 주지 않았다. 이 이유에 대해서는 지금까지 정보들을 숫자로 매핑시킨 이유와 함께 이제부터 알아보도록 하자.

 

정보들을 숫자로 매핑시킨 이유 & 코딩테스트 점수의 관리

먼저, 정보들을 숫자로 매핑시킨 이유에 대해서 부터 알아보도록 하자.

우리는 정보들을 숫자로 매핑시켰다. 그렇다면 아래의 예시를 다음과 같이 표현할 수 있다는 것을 의미한다.

예를 들어서 지원자의 정보로 "java backend junior pizza 10" 이라는 정보가 주어졌다고 가정해보자.

위에서 했듯이 이 정보를 숫자로 매핑한 결과를 적어보면 다음과 같다.

[ java / backend / junior / pizza / 10 ] = [ 2 / 1 / 1 / 2 / ? ]

이렇게 적어볼 수 있을 것이다. 그렇다면 이를 우리는 역으로 숫자만 보고도 어떤 정보를 의미하는 것인지 알 수 있을 것이다. 즉 ! [ 2 / 1 / 1 / 2 / ? ] 만 보고도 이 정보가 [ java / backend / junior / pizza / ? ] 를 의미한다라는 것을 알 수 있는 것이다.

본인은 이 숫자들을 "배열의 인덱스 처럼 사용하기 위해" 서 숫자로 매핑을 시켜 주었다.

그래서 본인이 만든 정보를 관리하기 위한 자료구조가 벡터이다.

바로, "vector<int> Group_Info[4][3][3][3]" 이다. 이와 같은 벡터를 선언해서 정보들을 관리해 주었는데, 각 인덱스가 의미하는 '4','3','3','3' 은 각 정보들이 가질 수 있는 최대 크기와 같다.

먼저, "개발언어"는 1, 2, 3 이라는 총 3개의 숫자가 나올 수 있다. 이 3개의 숫자를 관리하기 위해서 '4'칸을 만들어 주었고, 나머지 "직군", "경력", "소울푸드" 는 1, 2 라는 총 2개의 숫자가 나올 수 있는데, 이 2개의 숫자를 관리하기 위해서 '3'칸을 만들어 주었다.

그렇다면 이 벡터에 들어가는 데이터는 뭐가 있을까 ?? 바로 매핑을 시켜놓지 않은 "코딩테스트 점수" 가 들어간다.

다시 위에서 적어놓은 예를 가져와 보겠다.

"java backend junior pizza 10" 우리는 이 정보를 보고 [ 2 / 1 / 1 / 2 / 10 ] 으로 매핑을 시킬 수 있을 것이다.

그럼, 이렇게 매핑을 시켰다면 위에 선언해놓은 벡터인 Group_Info[2][1][1][2] 에 코딩테스트 점수인 '10'을 넣어주는 것이다.

즉, Group_Info[A][B][C][D] 가 의미하는 것은 "개발언어가 A이고, 직군이 B이고 경력이 C이고 소울푸드가 D인 지원자들의 코딩테스트 점수를 모아놓은 곳" 을 의미한다.

 

그런데 한가지 문제가 발생한다.

주어진 Query문에는 '-'가 존재한다는 것이다. 즉 ! 특정 정보를 고려하지 않는 Query문이 주어질 수도 있다.

예를 들어서 "- and backend and junior and pizza 10" 라는 Query문이 주어졌다고 가정해보자.

우리가 정보들을 숫자로 매핑시켰듯이 똑같이 숫자로 바꿔본다면 다음과 같을 것이다.

[ ? / 1 / 1 / 2 / 10 ] 으로 매핑이 될 것이다. 중요한건 '?' 부분이다. 개발언어를 고려하지 않는 Query문이다 보니, 우리가 했던 것 처럼 숫자로 매핑을 시킬 수가 없다.

더 큰 문제는, "- and backend and junior and pizza 10" 이 예시에서는 Group_Info[2][1][1][2] 에 들어있는 정보 또한 필요하다는 것이다. 왜 ? 개발언어를 고려하지 않기 떄문에, 개발언어가 뭐든 상관없이 backend, junior, pizza 만 만족시키면 되기 때문이다.

그래서 ! 본인은 하나의 정보를 가지고 총 16개의 부분에 매핑을 시켜 주었다.

"java backend junior pizza 10" 다시 이 정보를 가지고 진행해보자.

숫자로 매핑시키면 [ 2 / 1 / 1 / 2 / 10 ]  이다.

이 정보는 Group_Info[2][1][1][2] 에도 들어갈 수 있지만, Group_Info[0][1][1][2] 에도 들어갈 수가 있다.

0은 뭘 의미하는 것일까 ?? 바로 Query문에서 나올 수 있는 '-', 즉 ! 고려하지 않음을 의미한다.

또 어디에 들어갈 수 있을까 ?? [0][0][1][2] 에도 들어갈 수 있을 것이다. [0][0][0][2]에도 들어갈 수 있을 것이다.

즉 ! 들어갈 수 있는 모든 인덱스들의 조합을 적어보면 다음과 같다.

[2][1][1][2] 라는 정보가 들어갈 수 있는 곳

[2][1][1][2] / [0][1][1][2] / [2][0][1][2] / [2][1][0][2] / [2][1][1][0] / ..... / [0][0][0][0]

총 16가지가 있는데 너무 많다보니 구체적인건 코드로 확인을 해보자.

본인이 구현한 주어진 정보를 매핑시키는 부분이다.

int Check_State(int N, char C)
{
	if (N == 1)
	{
		if (C == 'c') return 1;
		if (C == 'j') return 2;
		if (C == 'p') return 3;
	}
	else if (N == 2)
	{
		if (C == 'b') return 1;
		if (C == 'f') return 2;
	}
	else if (N == 3)
	{
		if (C == 'j') return 1;
		if (C == 's') return 2;
	}
	else if (N == 4)
	{
		if (C == 'c') return 1;
		if (C == 'p') return 2;
	}

	return 0;
}

void Mapping_Group_Info(vector<int> Group_Info[4][3][3][3], string State, string Score)
{
	int L = Check_State(1, State[0]);
	int W = Check_State(2, State[1]);
	int C = Check_State(3, State[2]);
	int F = Check_State(4, State[3]);
	Group_Info[L][W][C][F].push_back(stoi(Score));
	Group_Info[0][W][C][F].push_back(stoi(Score));
	Group_Info[L][0][C][F].push_back(stoi(Score));
	Group_Info[L][W][0][F].push_back(stoi(Score));
	Group_Info[L][W][C][0].push_back(stoi(Score));
	Group_Info[0][0][C][F].push_back(stoi(Score));
	Group_Info[0][W][0][F].push_back(stoi(Score));
	Group_Info[0][W][C][0].push_back(stoi(Score));
	Group_Info[L][0][0][F].push_back(stoi(Score));
	Group_Info[L][0][C][0].push_back(stoi(Score));
	Group_Info[L][W][0][0].push_back(stoi(Score));
	Group_Info[0][0][0][F].push_back(stoi(Score));
	Group_Info[0][0][C][0].push_back(stoi(Score));
	Group_Info[0][W][0][0].push_back(stoi(Score));
	Group_Info[L][0][0][0].push_back(stoi(Score));
	Group_Info[0][0][0][0].push_back(stoi(Score));
}

위와 같이 총 16개의 부분에 들어갈 수가 있다.

 

다시 이야기해보면, 각각의 벡터에는 해당 조건을 만족하는 지원자들의 코딩테스트 점수가 들어있다.

본인은 이 코딩테스트 점수를 오름차순으로 정렬을 해 주었다. 왜 정렬을 해 주었는지는 아래에서 구체적으로 알아보도록 하자.

#2. Query문

#1의 과정이 끝났으면 문제를 90% 이상은 해결했다고 볼 수 있다.

Query문에 대한 관리는 매우 간단하다.

우리가 위에서 주어진 지원자들의 정보를 완벽하게 관리를 해 놓았기 때문에, 저 정보들에서 원하는 Query만 찾으면 되는 것이다.

Query문 또한 주어진 Query문을 정보들과 마찬가지로 숫자로 바꿔주면 된다.

이 때, 고려하지 않음을 뜻하는 '-'가 나오면 0으로 매핑을 시켜주면 된다. 어차피 우리는 지원자들의 정보를 관리할 때 관리하지 않는 경우까지 고려해서 모두 관리를 해놓았기 때문이다.

만약, Query문에 대한 정보를 숫자로 매핑했는데 [ A / B / C / D ] 라는 숫자가 나왔다고 가정해보자.

그럼 우리는 Group_Info[A][B][C][D]를 탐색하면서, 해당 벡터의 원소가 요구하는 코딩테스트 점수보다 더 크거나 같은 시점을 찾기만 하면 된다.

왜 ??? 어차피 우리는 코딩테스트 점수를 "오름차순으로 정렬"을 시켜놓았기 때문이다.

만약, [A][B][C][D] 에 총 10개의 원소가 들어있다고 가정해보자. 그리고 이 10개의 원소는 오름차순으로 정렬이 되어 있는 상태인데, 이 때 이 10개의 원소 중 3번째 원소가 요구하는 코딩테스트 점수보다 더 크다고 가정을 해보자.

그럼 조건에 부합하는 지원자의 수는 ?? 7명이라는 것을 알 수 있다. 왜냐하면 오름차순으로 정렬이 되어 있는데, 3번째 원소가 조건을 만족한다면, 당연하게도 4번째, 5번째,...,10번째 원소들 또한 조건을 만족할 수 있기 때문이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int Check_State(int N, char C)
{
    if (N == 1)
    {
        if (C == 'c') return 1;
        if (C == 'j') return 2;
        if (C == 'p') return 3;
    }
    else if (N == 2)
    {
        if (C == 'b') return 1;
        if (C == 'f') return 2;
    }
    else if (N == 3)
    {
        if (C == 'j') return 1;
        if (C == 's') return 2;
    }
    else if (N == 4)
    {
        if (C == 'c') return 1;
        if (C == 'p') return 2;
    }
 
    return 0;
}
 
void Mapping_Group_Info(vector<int> Group_Info[4][3][3][3], string State, string Score)
{
    int L = Check_State(1, State[0]);
    int W = Check_State(2, State[1]);
    int C = Check_State(3, State[2]);
    int F = Check_State(4, State[3]);
    Group_Info[L][W][C][F].push_back(stoi(Score));
    Group_Info[0][W][C][F].push_back(stoi(Score));
    Group_Info[L][0][C][F].push_back(stoi(Score));
    Group_Info[L][W][0][F].push_back(stoi(Score));
    Group_Info[L][W][C][0].push_back(stoi(Score));
    Group_Info[0][0][C][F].push_back(stoi(Score));
    Group_Info[0][W][0][F].push_back(stoi(Score));
    Group_Info[0][W][C][0].push_back(stoi(Score));
    Group_Info[L][0][0][F].push_back(stoi(Score));
    Group_Info[L][0][C][0].push_back(stoi(Score));
    Group_Info[L][W][0][0].push_back(stoi(Score));
    Group_Info[0][0][0][F].push_back(stoi(Score));
    Group_Info[0][0][C][0].push_back(stoi(Score));
    Group_Info[0][W][0][0].push_back(stoi(Score));
    Group_Info[L][0][0][0].push_back(stoi(Score));
    Group_Info[0][0][0][0].push_back(stoi(Score));
}
 
void Parsing_Info_Str(vector<string> Info, vector<int> Group_Info[4][3][3][3])
{
    for (int i = 0; i < Info.size(); i++)
    {
        int Idx = 0;
        string Temp = "";
        string Score = "";
        while (Idx < Info[i].length())
        {
            Score = "";
            Temp += Info[i][Idx];
            while (Idx < Info[i].length() && Info[i][Idx] != ' ')
            {
                Score += Info[i][Idx];
                Idx++;
            }
            Idx++;
        }
        Mapping_Group_Info(Group_Info, Temp, Score);
     }
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                for (int l = 0; l < 3; l++)
                {
                    sort(Group_Info[i][j][k][l].begin(), Group_Info[i][j][k][l].end());
                }
            }
        }
    }
}
 
void Mapping_Query_To_Info(vector<int> Group_Info[4][3][3][3], string State, string Score, vector<int> &answer)
{
    int L = Check_State(1, State[0]);
    int W = Check_State(2, State[1]);
    int C = Check_State(3, State[2]);
    int F = Check_State(4, State[3]);
 
    int Group_Num = Group_Info[L][W][C][F].size();
    int Find_Score = stoi(Score);
    int Cnt = 0;
    for (int i = 0; i < Group_Num; i++)
    {
        if (Group_Info[L][W][C][F][i] >= Find_Score) break;
        Cnt++;
    }
    answer.push_back(Group_Num - Cnt);
}
 
void Parsing_Query_Str(vector<string> query, vector<int> Group_Info[4][3][3][3], vector<int> &answer)
{
    for (int i = 0; i < query.size(); i++)
    {
        int Idx = 0;
        string Temp = "";
        while (Idx < query[i].length())
        {
            Temp += query[i][Idx];
            while (Idx < query[i].length() && query[i][Idx] != ' ')
            {
                Idx++;
            }
            if ('1' <= query[i][Idx + 1] && query[i][Idx + 1] <= '9') break;
            Idx += 5;
        }
        string Score = "";
        Idx++;
        while (Idx < query[i].length())
        {
            Score += query[i][Idx];
            Idx++;
        }
        Mapping_Query_To_Info(Group_Info, Temp, Score, answer);
    }
}
 
vector<int> solution(vector<string> info, vector<string> query) 
{
    vector<int> answer;
    vector<int> Group_Info[4][3][3][3];
    Parsing_Info_Str(info, Group_Info);
    Parsing_Query_Str(query, Group_Info, answer);
    return answer;
}