우선순위 퀴 : 비트마스킹 : 카카오2021 순위검색

풀이전략

  • 언어, 직군, 경력, 소울 푸드 를 구분 지어야 한다.

  • 모든 것이 선택되지 않더라도 점수를 이용해서도 카운팅이 가능하다는 점이 있다.

  • 입력값들 사이에 공백이 있으므로 stringstream을 사용하자.

  • 4차원 벡터 형식으로 진행하고, 인덱스의 값에 삽입하는 식으로 하므로
    info의 string을 int로 변환할 map이 필요하다.

  • 언어에서 cpp 선택,

    언어 : cpp, 자바, 파이썬
    직군 : back, front,
    경력 : 주니어, 시니어
    음식 : 치킨, 피자
    추가적으로 아무것도 선택하지 않았을 경우를 추가해야 하므로
    갯수를 한개씩 늘려야한다.

생각할 수 있는 단서

query에서 "- and - and - and - 150" 일때 6명의 infor 중
해당되는 것이 4개 있다.
-> 동일한 컨테이너에 한사람당 선택되지 않은 것들에 대한 정보가 6개 들어가 있다는 것이다.
그 컨테이너와 query[5]를 비교 했을때 150이상인 것들이 4개 존재한다는 것이다.

  • 동일하게 없는 부분에 대해서 컨테이너를 모두 삽입해야 겠다고 생각할 수 있으므로 벡터를 사용해야 한다.
    query의 "- and - and - and - 150"에서 4개가 나왔다는 것은
    info의 정보를 컨테이너에 넣은 상태에서 비교를 했다는 것이다.
  • 사용하고 안하고를 위해서 비트마스크를 사용한다.

풀이 과정

고민한 부분

  • 비트마스킹이랑 , string을 어떻게 연관 시킬까?

  • 여기서 일단 합쳤다.

    -> 비트마스킹 안쪽 반복문에서 어떻게 해서 나온 값들은 벡터의 인덱스 표현한 다음에 push_back 하면 될거 같다.

느낀점

1) 비트마스킹과 혼합되면서 어려워짐

2) 갯수를 파악하는 것이므로 150점이상인 갯수를 구하는 것이므로
-> upper_bound나 lower_bound를 사용하는 것인데,
그러기 위해서 정렬을 진행하는 것이다.
예를 들면
v[0][0][0][0]에 삽입된 값은 이렇게 인데, 갯수를 구하는 것이므로 정렬을 한후, upper_bound나 lower_bound를 이용해야 한다.

  • 그림의 순서대로 삽입이 된것이다.

    -> 정렬하면 50 - 80 - 150- 150 - 210- 260 으로 나열할 수 있다.
    lower_bound를 하면 2번째 인덱스를 가리키게 될 것이다.
    여기서 정답은 150이상인 수는 4개이다
    size() - index를 하면된다.

풀이전략

1) 언어 - 직군 - 경력 - 푸드
이므로 비트 연산자로 표현하면 0 ~ 15까지를 만들 수 있는 이를 이용하자.

어떤 점수 이상인 것을 알아내면 되므로

lower_bound를 사용하자.

소스코드

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

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    vector<int>v[4][3][3][3];
    map<string, int>m;
    
    m["-"] = 0;
    m["cpp"] = 1;
    m["java"] = 2;
    m["python"] = 3;
    
    m["backend"] = 1;
    m["frontend"] = 2;
    
    m["junior"] = 1;
    m["senior"] = 2;
    
    m["chicken"] = 1;
    m["pizza"] = 2;
    
    //소울 푸드 , 경력, 직군, 언어
    //   0       0     0     1 
    //   0       0     1     0
    //   0       0      1     1
    //   0       1     0     0
    
    
    //각 string을 언어, 직군, 경력, 소울 푸드로 분류해야 하므로 stingstream을 사용함.
    for(const string word : info)
    {
        stringstream ss;  
        ss<< word;
        
        string a, b, c, d;
        int score;
        
        ss >> a >> b >> c >> d >> score;
        int index[4] = {m[a], m[b], m[c], m[d]};
        //2, 1 , 1 , 2       
        //있고 없고를 구분해서 컨테이너에 넣어야 하니까 비트마스킹 표현은 맞다.
        for(int i = 0; i < (1 << 4); i++)
        {
            int k[4] = {0};
            //자릿수를 비교하는 거다.
            for(int j = 0; j < 4; j++)
            {
                if(i & (1 << j))
                {
                    k[j] = index[j];
                }
            }
            //없는 것을 0번 인덱스로 설정하는 거를 알 수 있으므로
            //삽입하면 될거 같은데...
            v[k[0]][k[1]][k[2]][k[3]].push_back(score);
        }
        
    }
    
    for (int a = 0; a < 4; a++)
	{
		for (int b = 0; b < 3; b++)
		{
			for (int c = 0; c < 3; c++)
			{
				for (int d = 0; d < 3; d++)
				{
					sort(v[a][b][c][d].begin(), v[a][b][c][d].end());
				}

			}
		}
	}
    //query 와 비교하면 된다. 
    
    for(const string word : query)
    {
        stringstream ss;
        ss << word;
        string a, b, c,d,tmp;
        int score;
        ss >> a >> tmp >> b >> tmp >> c >> tmp >>d >> score;
        
        auto list = v[m[a]][m[b]][m[c]][m[d]]; // 벡터의 모든 요소
        auto iter = lower_bound(list.begin(), list.end(), score);
        answer.push_back(list.end() - iter);
    }
    

    return answer;
}
int main() {

	vector<string>s = { "java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50" };
	vector<string>q = { "java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150" };

	solution(s, q);
	return 0;

}

좋은 웹페이지 즐겨찾기