탐색이 지저분 하다면 이분탐색
문제 풀이 단계
(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번 해야하고, 주요 알고리즘을 쓰게끔 만들었기 때문에
좋은 문제 같다.
사실 이 문제는 예전에 푼 문제다. 예전에 한 티스토리 블로그에 정리글을 남겨둬서 문제 다시 푼 김에 찾아봤는데, 똑같이 헤맸었다ㅠㅠ... 발전 쿠다사이...
곧 카카오 공채가 다가온다. 솔직히 합격하리란 기대는 안 한다. 넘 힘 빠져ㅠ
그럼에도 노력할 것이다! 힘내줘 파닥파닥...