우선순위 퀴 : 비트마스킹 : 카카오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 하면 될거 같다.
느낀점
언어, 직군, 경력, 소울 푸드 를 구분 지어야 한다.
모든 것이 선택되지 않더라도 점수를 이용해서도 카운팅이 가능하다는 점이 있다.
입력값들 사이에 공백이 있으므로 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 하면 될거 같다.
느낀점
비트마스킹이랑 , 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;
}
Author And Source
이 문제에 관하여(우선순위 퀴 : 비트마스킹 : 카카오2021 순위검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kwt0124/카카오2021-순위검색
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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;
}
Author And Source
이 문제에 관하여(우선순위 퀴 : 비트마스킹 : 카카오2021 순위검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwt0124/카카오2021-순위검색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)