프로그래머스 - 순위 검색 / C++

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

코딩테스트 연습 - 순위 검색

구현이 까다로웠던 문제였다.

비트마스크와 이분탐색을 사용해서 문제를 해결했다.

 

문제 풀이

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를 찾은 후에 답을 찾아내었다.