programmers.co.kr/learn/courses/30/lessons/72412
코딩테스트 연습 - 순위 검색
["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"] ["java and backend and junior and pizza 100","pyt
programmers.co.kr
구현이 까다로웠던 문제였다.
비트마스크와 이분탐색을 사용해서 문제를 해결했다.
문제 풀이
map<string, int> m 을 선언한 후에 각 데이터를 파싱해서 넣어줄 것이다.
string을 이용하여 저장하지 않은이유는 bit를 쓰면 간편하게 비교를 할 수 있기 때문이다.
m["cpp"] = 1 << 8;
m["java"] = 1 << 7;
m["python"] = 1 << 6;
m["backend"] = 1 << 5;
m["frontend"] = 1 << 4;
m["junior"] = 1 << 3;
m["senior"] = 1 << 2;
m["chicken"] = 1 << 1;
m["pizza"] = 1;
각 항목별로 비트 마스킹을 하였다.
"java backend junior pizza 150" 이런 예제가 들어왔으면
이는 비트로 0b010101001 로 나타 낼 수 있다.
시간의 효율성이 있는 문제이므로 각 쿼리마다 연산과정을 줄이기 위해 데이터를 저장하는 방법을 생각해야 했다.
"python frontend senior chicken" 이 예제로 들어온다면 모든 쿼리에 대한 결과를 저장해 주어야 했다.
"- - - -"
"python - - - "
"- frontend - -"
"- - senior -"
"- - - chicken"
"python frontend - -"
"python - senior -"
"python - - chicken"
"- frontend senior -"
"- frontend - chicken"
"- - senior chicken"
"python frontend senior -"
"python frontend - chicken"
"python - senior chicken"
"- frontend senior chicken"
"python frontend senior chicken"
총 16가지 경우에 대해서 점수를 저장해 주었다.
이렇게 저장한 데이터를 모두 정렬해주고
lower_bound함수를 이용해서 index를 찾은 후에 답을 찾아내었다.
'Algorithm' 카테고리의 다른 글
프로그래머스 - 매출 하락 최소화 / C++ (2) | 2021.03.08 |
---|---|
프로그래머스 - 합승 택시 요금 / C++ (0) | 2021.03.05 |
프로그래머스 - 신규 아이디 추천 / C++ (0) | 2021.03.03 |
백준 - 2146번(다리 만들기) / C++ (0) | 2021.02.27 |
백준 - 16947번(서울 지하철 2호선) / C++ (1) | 2021.02.26 |