[프로그래머스] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT

파닥몬·2022년 9월 20일
0

KAKAO를 풉니다.

목록 보기
8/12
post-thumbnail

⚙️ 알고리즘 분류 : 조합+이분탐색

🔠 언어 : c++

🤫 힌트.

탐색이 지저분 하다면 이분탐색

✏️ 풀이.

문제 풀이 단계
(1) 문자열을 공백 기준으로 쪼갠다.
(2) 조합으로 쪼갠 문자열마다 -가 들어가는 모든 경우의 수(-가 들어간 문자열)를 만든다. 그리고 경우의 수를 다 붙여서 하나의 문자열로 만든다.
=> 1234가 조건이라면 ----, 1---, -2-4
(3) map의 key는 붙인 문자열, value는 점수의 배열로 두고 value에 점수를 추가한다.
=> ----(100), 1---(100), -2-4(100)
(4) 제대로 된 탐색을 하기 위해 value에 있는 점수들을 정렬한다.
(5) 이분 탐색을 사용하여 적절한 답을 찾는다.

➡️ 4번 정렬해주는 과정을 은근 안 챙긴다. 이거 안 챙기면 탐색 제대로 안 되니까 잊지 말자!

⚠️ 헤맨 부분.

1) info를 어떻게 저장하지...?
문제를 어떻게 풀지 생각하면서 자꾸 dropdown이 생각났다.
map을 사용해서 m[java][frontend][-] 뭐 이런 식으로...
처음엔 구조체를 만들었다. 구조체로 하다가 잘 안돼서 전에 푼 코드를 봤는데,
두 가지 놀란 부분이 있었다.

첫 번째는 그냥 다 붙여서 문자열로 만든 것이었다. "javabackendjuniorpizza"
해당 조건에 정확하게 들어맞는 사람들 중, 특정 점수 이상의 사람 수를 찾는 것이기에
문자열로 만들어도 상관이 없다...!

두 번째는 -가 들어가는 경우의 수를 다 만든 것이다. 사실 구조체 하다가 전에 푼 코드를 푼 건 query의 - 부분을 어떻게 처리할지 고민돼서 였다.
그래서 봤더니 -가 들어간 경우의 수를 다 만들고, 매번 점수를 저장했다.

두 번째 부분은 이 문제와 비슷하다.
[프로그래머스] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT
(원래 이 문제도 오마카세 였는데, 지금 이 문제가 더 좋은 것 같아서 오마카세 박탈했다.)

2) 5252... 탐색은 역시 00탐색이라구...!
query에 맞는 info를 찾을 때 그냥 무식하게 for문 돌렸다.
사실 for문 쓰면서도 '아 이거 시간초과 날 것 같은데...' 생각을 했다.
역시나... 시간 초과...

오랜만에 코테를 해서 그런지, 진리처럼 생각하는 것이 있다.

탐색은.. 역시 이분탐색...!

시간 초과가 난다면 이분 탐색을 사용해야 한다. 이 생각을 못해서 헤맸다...

👩🏻‍💻 코드.

#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <iostream>
#include <algorithm>
#define mp make_pair
using namespace std;
map<string, vector<int>> m;

// c++로 문자열 쪼개는 건 정말 자주 나오니까 숙지하자!
vector<string> split(string s){
    vector<string> result;
    string buffer;
    istringstream ss(s);
    while(getline(ss, buffer, ' ')){
        if(buffer=="and") continue;
        result.push_back(buffer);
    }
    return result;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    for(int i=0; i<info.size(); i++){
        vector<string> s=split(info[i]);
        int score=stoi(s[4]);
        vector<bool> mark(4, true);
        // 조합으로 모든 경우의 수를 만든다.
        for(int j=-1; j<4; j++){
        	// 무조건 false로 만들어야 한다. 그 이유는 위의 메뉴 리뉴얼 문제 참고염><
            if(j>=0) mark[j]=false;
            do{
                string tmp="";
                for(int k=0; k<mark.size(); k++){
                    if(!mark[k]) tmp+="-";
                    else tmp+=s[k];
                }
                m[tmp].push_back(score);
            }while(next_permutation(mark.begin(), mark.end()));
        }
    }
    for(auto it=m.begin(); it!=m.end(); it++){
        sort(it->second.begin(), it->second.end());
    }
    for(int i=0; i<query.size(); i++){
        vector<string> q=split(query[i]);
        string tmp="";
        for(int j=0; j<4; j++) tmp+=q[j];
        int score=stoi(q[4]), cnt=0;
        vector<int> v=m[tmp];
        
        // 이분 탐색
        int start=0, end=v.size()-1;
        while(start<=end){
            int mid=(start+end)/2;
            if(v[mid]>=score){
                end=mid-1;
                cnt=v.size()-mid;
                
            }
            else start=mid+1;
        }
        answer.push_back(cnt);
    }
    return answer;
}

😎 후기.

딱 풀고나서 와, 진짜 잘 만들었다는 생각을 했다.
주요 생각을 2번 해야하고, 주요 알고리즘을 쓰게끔 만들었기 때문에
좋은 문제 같다.

사실 이 문제는 예전에 푼 문제다. 예전에 한 티스토리 블로그에 정리글을 남겨둬서 문제 다시 푼 김에 찾아봤는데, 똑같이 헤맸었다ㅠㅠ... 발전 쿠다사이...

곧 카카오 공채가 다가온다. 솔직히 합격하리란 기대는 안 한다. 넘 힘 빠져ㅠ
그럼에도 노력할 것이다! 힘내줘 파닥파닥...

profile
파닥파닥

0개의 댓글