12주차 알고리즘 풀기 이제 다시 삼단계 갑시다.

코테시즌을 맞아, 보안기사는 하는수 없이 내려두고(확진자 너무 많아서 치러가기도 무서워요...) 알고리즘에 다시 집중해보자

카카오 블라인드 리크루트먼트 문제풀기(2019년)

 

 

 

1. 오픈 채팅방

https://programmers.co.kr/learn/courses/30/lessons/42888

코딩테스트 연습 - 오픈채팅방

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

vector<string> split_record(string r){
    vector<string> a;
    string temp = "";
    for(int i = 0; i < r.size(); i++){
        if(r[i] == ' '){
            a.push_back(temp);
            temp = "";
        }else{
            temp += r[i];
        }
    }
    
    a.push_back(temp);
    return a;
}

vector<string> solution(vector<string> record) {
    vector<string> answer;
    vector<pair<string, string>> before;
    map<string, string> m;
    
    for(int i = 0; i < record.size(); i++){
        vector<string> temp = split_record(record[i]);
        // if(temp[0] == "Enter" || temp[0] == "Change" )
        //     cout << temp[0] << " " << temp[1] << " " << temp[2] << "\n";
        // else{
        //     cout << temp[0] << " " << temp[1] << "\n";
        // }
        
        if(temp[0] == "Enter"){
            m[temp[1]] = temp[2];
            before.push_back({temp[1], "님이 들어왔습니다."});
        }else if(temp[0] == "Leave"){
            before.push_back({temp[1], "님이 나갔습니다."});
        }else if(temp[0] == "Change"){
            m[temp[1]] = temp[2];
        }
    }
    
    for(int i = 0; i < before.size(); i++){
        answer.push_back(m[before[i].first] + before[i].second);
    }
    return answer;
}

쉬운문제이나, c++을 한동안 안했더니 조금 혼동이 왔다. 

카카오 문제가 무조건 다 어려운게 아니었다는 깨달음이 왔다. 

map함수 사용법이 헷갈렸다. 그리고 생각보다 스트링관련 함수는막 어려운걸 알고있을 필요가 없다 

 

2. 실패율

 

코딩테스트 연습 - 실패율

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b){
    long long n1 = a.second.first;
    long long n2 = b.second.first;
    
    if(b.second.second != 0){
        n1 *= b.second.second;
    }
    if(a.second.second != 0){
        n2 *= a.second.second;
    }
    
    if(n1 != n2){
        return n1 > n2;
    }else{
        return a.first < b.first;
    }
    
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int, pair<int, int>>> fr(N+2, {0, {0, 0}});
    // index, 분자, 분모
    for(int i = 0; i < stages.size(); i++){
        fr[stages[i]].second.first++;
    }
    
    int acc = 0;
    for(int i = 1; i < N+1; i++){
        fr[i].second.second = (stages.size() - acc);
        fr[i].first = i;
        acc += fr[i].second.first;
    }

    sort(fr.begin() + 1, fr.end() - 1, comp);
    
    for(int i = 1; i < N+1; i++){
        answer.push_back(fr[i].first);
    }
    return answer;
}

문제가 어려운건 아닌데, 분수처리할때 에러가 많이 나는거같다. 나는 분수

a / b 와 c/d 를 비교하기 위해서 a * d와 c * b를 비교하기로했다. 

그런데 b나 d 가 0인경우를 처리를 어떻게 할지 감을 못잡아서 계속 23, 24번에서 오류가 났다. 

그냥 간단하게,

d 가 0이 아니면 a에 곱하고, 

b 가 0이 아니면 c에 곱하는 방식으로 해결했다. 

 

d나 b가 0이면 각각 c와 d는 자동으로 0이다. 

그래서 다른 하나는 무조건 더크거나, 같으면 인덱스로 비교를 한다. 

 

엄청 어렵다기보다는 내머리는 이런 말귀는 잘못알아듣는거같다. 

 

 

 

 

3. 후보키(못풀었음)

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int answer = 0;
vector<int> selected; // 선택된 칼럼

void func(vector<vector<string>> relation, vector<int> selected, int start){
    int col = relation[0].size();
    int s = relation.size();

    vector<string> acc(s, ""); // 앞에 누적된 값들 계산 칼럼 1,2가 선택됬을때 누적값
    for(int i = 0; i < s; i++){
        string cur = "";
        for(int j = 0; j < selected.size(); j++){
            cur += relation[i][selected[j]] + ' ';
        }
        acc[i] = cur;
    }
    
    vector<int> next;
    for(int i = start+1; i < col; i++){
        //칼럼 1, 2가 선택되었고, start가 3이면 각 키에 start칼럼의 값을 더함
        map<string, int> m;
        bool flag = true;
        for(int j = 0; j < s; j++){
            string cur = acc[j] + " " + relation[j][i];
            if(m.count(cur) == 0){
                m[cur] = 1;
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            answer++;
        }
        else{
            next.push_back(i);
        }
    } 
    
    for(int i = 0; i < next.size(); i++){
        if(next[i] >= col-1)
            continue;
        selected.push_back(next[i]);
        func(relation,  selected, next[i]);
        selected.pop_back();
    }  
}

int solution(vector<vector<string>> relation) {
    func(relation, selected, -1);
    return answer;
}

이문제는 두고두고 다시 풀어봐야할 것 같다. 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int answer = 0;
int column_size;
int row_size;
queue<vector<int>> q;

int solution(vector<vector<string>> relation) {
    column_size = relation[0].size();
    row_size = relation.size(); 
    
    // 칼럼 한개씩 선택했을때 중복없는 애들 확인
    for(int i = 0; i < column_size; i++){
        map<string, int> checker;
        bool flag = true;
        for(int j = 0; j < row_size; j++){
            if(checker.count(relation[j][i]) == 0){
                checker[relation[j][i]] = 1;
            }else{
                flag = false;
                break;
            }
        }
        if(flag == true){
            answer++;
        }else{
            vector<int> temp(1, i);
            q.push(temp);
        }
    }
    
    while(!q.empty()){
        vector<int> selected = q.front();
        q.pop();
        
        vector<string> acc(row_size, "");
        for(int i = 0; i < row_size; i++){
            string temp = "";
            for(int j = 0; j < selected.size(); j++){
                temp += (relation[i][selected[j]] + ' ');
            }
            acc[i] = temp;
        }
        
        int start = selected[selected.size() -1] + 1;
 
        for(int i = start; i < column_size; i++){
            map<string, int> checker;
            bool flag = true;
            for(int j = 0; j < row_size; j++){
                string temp = acc[j] + " " + relation[j][i];
                // cout << temp << " ";
                if(checker.count(temp) == 0){
                    checker[temp] = 1;
                }else{
                    flag = false;
                    break;
                }
            }
            
            if(flag == true){
                answer++;
            }else{
                selected.push_back(i);
                q.push(selected);
                selected.pop_back();
            }
        }
               
    }
    
    return answer;
}

큐로 풀어도 안됨. 이문제는 내가 뭔가 이해를 잘못하고 있는것 같음