2019 KAKAO BLIND RECRUITMENT 풀이 모음

1번

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

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

---

접근방법

단순 구현 문제였다. 해시를 활용해서 아이디를 이름에 매칭 시켜서 풀면 쉽게 해결이 된다.

---

실수

한 큐에 해결했습니다. O_O

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

map<string, string> db;
vector<string> solution(vector<string> record) {
    vector<string> answer;

    vector<pair<string, string>> log;
    for(auto s : record){
        string cmd, id, name;
        stringstream ss(s);
        ss >> cmd >> id >> name;

        if(cmd == "Enter"){
            db[id] = name;
            log.push_back({id, "님이 들어왔습니다."});
        }
        else if(cmd == "Leave"){
            log.push_back({id, "님이 나갔습니다."});
        }
        else if(cmd == "Change"){
            db[id] = name;
        }
    }

    for(auto p : log){
        answer.push_back(db[p.first] + p.second);
    }
    return answer;
}

int main(){
    vector<string> record = {"Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"};
    vector<string> ret = solution(record);
    for(auto s : ret){
        cout << s <<"\n";
    }
}

---

2번

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

코딩테스트 연습 - 실패율

 

---

접근방법

1. 각 스테이지에 남아있는 인원과 시도한 인원들에 대한 배열을 구해줍니다.

2. 문제의 조건 (남아있는 사람 / 시도한 사람)을 활용해서 실패율을 구해줍니다.

---

실수

한 큐에 해결했습니다 O_O

---

정답 코드

/**
 * 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수
 */
#include<bits/stdc++.h>

using namespace std;
const int MAX = 502;
int remainPeople[MAX];
int tryPeople[MAX];

bool cmp(pair<int,double> a, pair<int,double> b){
    if(a.second != b.second){
        return a.second > b.second;
    }
    else if(a.second == b.second){
        return a.first < b.first;
    }
    return false;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    for(auto n : stages){
        remainPeople[n]++;
        //n개의 층까지 도달한것은 n이전의 층들을 도달한것이므로 점수를 더해준다.
        for(int i = 1; i <= n; i++){
            tryPeople[i]++;
        }
    }
    vector<pair<int,double>> info;
    for(int i = 1; i <= N; i++){
        //시도한 사람이 없는 경우 실패율은 0이므로 예외처리
        if(tryPeople[i] == 0){
            info.push_back({i, 0});
            continue;
        }
        //문제의 조건을 활용하여 정보를 갱신한다.
        info.push_back({i,remainPeople[i] / double(tryPeople[i])});
    }
    //실패율에 비례한 정렬(문제조건)
    sort(info.begin(), info.end(), cmp);
    for(int i = 0; i < info.size(); i++){
        answer.push_back(info[i].first);
    }
    return answer;
}

int main(){
    vector<int> ret = solution(5, {2,1,2,6,2,4,3,3});
    for(auto a : ret)
        cout << a << " ";
    cout <<"\n";
}

---

3번

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

코딩테스트 연습 - 후보키

 

---

접근방법

정말 정신이가 가출해버리게 만든 문제였습니다. 문제를 잘못 이해한 게 가장 큰 원인이었습니다. 문제의 핵심 요지는 속성 즉 열이 순차적으로 조합을 이루는 모든 과정을 만들면서 후보 키를 만들어야 하는 문제입니다. 예를 들어 1개로 만들어질 수 있는 모든 조합, 2개로 만들어질 수 있는 모든 조합 ~ N개로 만들 수 있는 모든 조합의 형식으로 진행이 되어야 합니다. 저는 각각의 경우에 1, 2, 3 순으로 만들어지는 조합을 만들어서 처음에 실패를 하였고 많은 시간을 소모했습니다.

 

전체적인 진행 과정은

1. 원하는 길이의 모든 조합을 순서대로 만들어준다.

2. 조합의 길이만큼 탐색이 진행되면 최소성과 유일성을 확인해준다.

3. 확인이 되면 결과값을 1 올려준다.

입니다.

과정마다 진행해야 하는 예외처리나 중요 로직은 주석을 첨부하였습니다.

---

실수

1. 조합의 순서를 잘못 구현하였다.

---

정답 코드

#include <bits/stdc++.h>

using namespace std;

int cLen, retCnt;
vector<vector<string>> Board;
vector<vector<int>> candidate;
vector<int> v;
bool visited[9];

//A fuction that returns a true or false, if combination have only one as a candidate key
bool isUnique(){
    vector<string> evaltionList;
    for(int i = 0; i < Board.size(); i++){
        string sentance;
        for(int j = 0; j < v.size(); j++){
            int pos = v[j];
            sentance += Board[i][pos];
        }
        if (find(evaltionList.begin(), evaltionList.end(), sentance) == evaltionList.end())
            evaltionList.push_back(sentance);
        else
            //if the candidate key comes out once again, it does not satisfy the unique conditions
            return false;

    }
    return true;
}

//A funtion isMinimalty return a true, if combination have most small of the key
bool isMinimalty(){
    for(int i = 0; i < candidate.size(); i++){
        bool outFlag = false;
        for(int j = 0; j < candidate[i].size(); j++){
            int testNum = candidate[i][j];
            if(find(v.begin(), v.end(), testNum) == v.end()){
                outFlag = true;
                break;
            }
        }
        if(outFlag == false)
            return false;
    }
    return true;
}

bool check(){
    if(isUnique() && isMinimalty()){
        return true;
    }
    else
        return false;
}

void DFS(int idx, int cnt , int totalCnt){
    if(cnt == totalCnt){
        if(check()){
            //Candidate keys that have come out at least onece must be stored. cos when they are needed to verity the minimun
            candidate.push_back(v);
            retCnt++;
        }
        return;
    }

    for(int i = idx; i < cLen; i++){
        //only checked unused arr
        if(!visited[i]){
            visited[i] = true;
            //process of putting the combination factor
            v.push_back(i);
            DFS(idx + 1, cnt + 1, totalCnt);
            v.pop_back();
            visited[i] = false;
        }
    }
}
int solution(vector<vector<string>> board) {
    cLen =  board[0].size();
    Board = board;
    //this is circumstance of make of all of the combination
    for(int i = 1; i <= cLen; i++)
        DFS(0, 0, i);
    return retCnt;
}

int main() {
    int a = solution({{"100", "ryan",   "music",    "2"},
                      {"200", "apeach", "math",     "2"},
                      {"300", "tube",   "computer", "3"},
                      {"400", "con",    "computer", "4"},
                      {"500", "muzi",   "music",    "3"},
                      {"600", "apeach", "music",    "2"}});
    cout << a << "\n";
}

---

4번

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

코딩테스트 연습 - 무지의 먹방 라이브

---

접근방법

문제의 조건 때문에 O(N ^ 2)등 시간 복잡도가 높은 알고리즘을 사용하면 효율성 테스트에 실패하는 문제입니다. 문제의 조건을 보고 그리디 알고리즘으로 풀어야겠다고 생각하였습니다. 아이디어는 k의 시간을 빠르게 단축시키는 것을 핵심으로 잡아야 합니다.(k의 단축이 끝나면 회전이 끝나는 것과 의미가 같다.) food_time에서 가장 작은 음식 시간이 가장 빠르게 0이 되므로 우선순위 큐를 사용하여 큐에 음식 시간을 모두 넣어준 후 가장 작은 시간 순서대로 pop을 해줍니다. 이후 (뽑은 음식의 시간 - 이전 음식 시간) -before * 큐의 큐기가 k보다 작다면 k에서  (뽑은 음식의 시간 - 이전 음식 시간) -before만큼 감소시켜줍니다. 이유는 한 사이클이 음식의 배열에서 돌면은 모든 음식의 시간이 -1씩 감소됩니다. 그런데 이 시간들이 k보다 더 크게 감소하려고 그러면 문제의 논리에 어긋납니다. 그러므로 위의 수식 조건을 만족할 때까지만 반복을 진행합니다. before은 이전 음식의 시간을 의미하며 빼주는 이유를 이해하기 위해서는 우선순위 큐에 있는 원소들이 pop 될 때마다 실제로는 배열에서 pop 된 음식의 시간만큼 남아있는 음식들의 시간도 단축이 돼야 한다는 의미를 이해해야 합니다. 이러한 논리를 이해하면 이전 음식의 시간을 빼는 것을 이해할 수 있습니다.

---

실수

 

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

int solution(vector<int> food_times, long long k) {
    long long sum = 0, before = 0;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pfood_times;
    for (int i = 0; i < food_times.size(); i++) {
        sum += food_times[i];
        pfood_times.push(make_pair(food_times[i], (i + 1)));
    }
    //if sum Value is less then or equal to k. it is mean search is impossible
    if (sum <= k)    return -1;
    while ((pfood_times.top().first - before) * pfood_times.size() <= k) {
        k -= (pfood_times.top().first - before) * pfood_times.size();
        //Update the time of the previous food to the time of the current food.
        before = pfood_times.top().first;
        pfood_times.pop();
    }
    vector<pair<int, int>> ftimes;
    while (!pfood_times.empty()) {
        ftimes.push_back(make_pair(pfood_times.top().second, pfood_times.top().first));
        pfood_times.pop();
    }
    //Arrange the food in the order of beginning
    sort(ftimes.begin(), ftimes.end());
    return ftimes[k % ftimes.size()].first;
}

int main(){
    vector<int> food_times = {3,1,2};
    int k = 5;
    cout << solution(food_times, k) <<"\n";
}

---

5번

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

코딩테스트 연습 - 길 찾기 게임

 

---

접근방법

1. Tree를 만들어준다.

  1-1. 트리를 이루는 노드의 정렬 기준이 필요하다

  1-2. 트리의 y축이 가장 높아야 하며 y축이 같을 경우 왼쪽부터 두기 위해 x값이 작은 순으로 정렬을 진행한다

2. preOrder와 postOrder를 진행한다. 

---

실수

1.makeTree 함수를 구성할 때 right에 대한 포인터 참조 부분에서 잘못 구현을 했다.

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

struct Tree{
    int idx;
    int x, y;
    Tree *left, *right;
};

bool cmp(Tree a , Tree b){
    if(a.y != b.y){
        return a.y > b.y;
    }
    else if(a.x != b.x){
        return a.x < b.x;
    }
    return false;
}

vector<Tree> tree;

void preOrder(const Tree *root, vector<int> &sol){
    if(root == NULL)
        return ;
    sol.push_back(root->idx);
    preOrder(root->left, sol);
    preOrder(root->right, sol);

}

void postOrder(const Tree *root, vector<int> &sol){
    if(root == NULL)
        return ;
    postOrder(root->left, sol);
    postOrder(root->right, sol);
    sol.push_back(root->idx);
}

void makeTree(Tree *Root, Tree *cur){
    if(Root->x > cur->x){
        if(Root->left == NULL){
         Root->left = cur;
         return;
        }
        makeTree(Root->left, cur);
    }
    else{
        if(Root->right == NULL){
            Root ->right = cur;
            return;
        }
        makeTree(Root->right, cur);
    }
}

vector<vector<int>> solution(vector<vector<int>> nodeInfo) {
    vector<vector<int>> answer;
    for(int i = 0; i < nodeInfo.size(); i++){
        int x = nodeInfo[i][0];
        int y = nodeInfo[i][1];
        tree.push_back({i + 1, x, y, NULL, NULL});
    }
    sort(tree.begin(), tree.end(), cmp);
    Tree *root = &tree[0];
    for(int i = 1; i < tree.size(); i++){
        makeTree(root, &tree[i]);
    }
    vector<int> preArr, postArr;
    preOrder(root, preArr);
    postOrder(root, postArr);
    answer.push_back(preArr), answer.push_back(postArr);
    return answer;
}

int main(){
    vector<vector<int>> ret = solution({{5,3}, {11,5}, {13,3}, {3,5}, {6,1}, {1,3}, {8,6}, {7,2}, {2,2}});
    for(auto v : ret){
        for(int n : v){
            cout<< n <<" ";
        }
        cout <<"\n";
    }
}

---

6번

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

코딩테스트 연습 - 매칭 점수

---

접근방법

1.webPage의 번호를 담는 idx 변수, 기본점수를 의미하는 basicPoint, 하이퍼링크의 주소를 가지고 있는 outlink, 링크 점수를 의미하는 linkPoint, 매치 점수를 의미하는 matchPoint 변수를 가지는 구조체를 선언한다.

2. 구조체의 변수값을 구하기 위한 함수를 설정한다. 이러한 함수는 master에서 관리한다.

 2-1.  함수와 동작들을 정의하기 위한 master 구조체를 선언한다.

---

실수

단어를 구하는 함수 cntWord 함수를 구현할 때 stringStream으로 구현해서 구현을 했는데 232$232같은 경우를 구분하는 게 불가능해서 재구현을 했다.

---

정답 코드

#include<bits/stdc++.h>

using namespace std;

struct web {
    int idx;
    int basicPoint;
    vector<string> outLink;
    double linkPoint;
    double matchPoint;
};

map<string ,int> webNum;

bool Cmp(web a, web b){
    if(a.matchPoint != b.matchPoint){
        return a.matchPoint > b.matchPoint;
    }
    if(a.matchPoint == b.matchPoint){
        return a.idx < b.idx;
    }
    return false;
}

struct master {
    string word;
    vector<string> pages;
    master(string word, vector<string> pages) : word(word), pages(pages) {}

    vector<web> makeInfo(){
        vector<web> info;
        word = smallLetter(word);
        int idx = 0;
        for(auto str : pages){
            string parsingStr = smallLetter(str);
            string myUrl = findMyUrl(str);
            webNum[myUrl] = idx + 1;
            int basicPoint = cntWord(parsingStr);
            vector<string> outLink = findOutLink(parsingStr);
            info.push_back({idx++, basicPoint, outLink, 0.0, 0.0});
        }
        for(auto i : info){ //i는 info의 위치
            for(auto s : i.outLink){//s는 i번째 web의 외부링크들을 의미
                if(webNum[s] == 0)
                    continue;
                info[webNum[s] - 1].linkPoint += (double)i.basicPoint / (double)i.outLink.size();
            }
        }
        for(auto &i : info){
            i.matchPoint = (double)i.basicPoint + (double)i.linkPoint;
        }
        sort(info.begin(), info.end(), Cmp);
        return info;
    }

    string findMyUrl(string str){
        string ret;
        int pos1 = str.find("<meta property=\"og:url\" content=\"https://");
        pos1 += string("<meta property=\"og:url\" content=\"https://").length();
        while(str[pos1] != '\"'){
            ret += str[pos1++];
        }
        return ret;
    }

    string smallLetter(string str){
        string ret;
        for(auto c : str){
            if(c == '\n'){
                ret += " ";
            }
            else if(c >= 'A' &&  c <= 'Z')
                ret += c + 32;
            else
                ret += c;
        }
        return ret;
    }

    int cntWord(string str){
        int wordCnt = 0;
        int pos1 = str.find("<body>");
        pos1 += 7;
        int pos2 = str.find("</body>");
        pos2 += 7;
        str = str.substr(pos1, pos2 - pos1);

        string cur = "";
        for(int i = 0; i < str.length(); i++){
            if(isalpha(str[i]) == 0){
                if(cur == word)
                    wordCnt++;
                cur ="";
            }
            else
                cur += str[i];
        }
        return wordCnt;
    }

    vector<string> findOutLink(string str){
        vector<string> ret;
        int pos = str.find("<a href=\"https://");
        while(pos != -1){
            pos += string("<a href=\"https://").length();
            string url = "";
            while(str[pos] != '\"'){
                url += str[pos++];
            }
            ret.push_back(url);
            str = str.substr(pos);
            pos = str.find("<a href=\"https://");
        }
        return ret;
    }
};

int solution(string word, vector <string> pages) {
    int answer = 0;
    master op(word, pages);
    vector<web> ret = op.makeInfo();
    answer = ret[0].idx;
    return answer;
}

int main() {
    cout << solution("blind",
                     {"<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://a.com\"/>\n</head>  \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>",
                      "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://b.com\"/>\n</head>  \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>",
                      "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://c.com\"/>\n</head>  \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"
                     }) <<"\n";
    cout <<solution("Muzi", {"<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head>  \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head>  \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"});
}

---

7번

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

코딩테스트 연습 - 블록 게임

---

접근방법

문제 해결에 대한 아이디어가 떠오르지 않아 밑에 블로그를 참조했다.

https://yabmoons.tistory.com/489

[ 프로그래머스 블록 게임 (Lv4) ] (C++)

1. 가능한 도형을 분류한다.

2. 0,0부터 탐색 시작

 2-1. 0이 아닌 경우 탐색을 시작한다.

 2-1. 0인 경우에는 continue;

3. 탐색 가능한 도형인지 확인을 한다.

 3-1. 불가능한 경우 가능한 다른 도형을 확인해본다.

4. 가능한 경우 y축 값을 0까지 올려서 가능한지 확인한다. 

 4-1. 불가능할 경우 가능한 다른 도형을 확인한다

5. 4번까지 가능한 시작점을 x축을 -1로 변경 후 retCnt를 올려주고 도형은 지워준다.

---

실수

4번 구현에서 실패할 경우 탐색을 종료해주게 하여서 실패를 받았다. 다른 도형이 가능한지 확인을 해줘야 했는데 그러지 못하여 논리 오류가 발생했다.

---

정답 코드

#include<bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int figure[5][6][2]{
    {{0, 0}, {1, 0}, {1, 1},  {1, 2},  {0, 1},  {0, 2}},
    {{0, 0}, {1, 0}, {2, 0},  {2, -1}, {0, -1}, {1, -1}},
    {{0, 0}, {1, 0}, {2, 0},  {2, 1},  {0, 1},  {1, 1}},
    {{0, 0}, {1, 0}, {1, -1}, {1, -2}, {0, -1}, {0, -2}},
    {{0, 0}, {1, 0}, {1, -1}, {1, 1},  {0, -1}, {0, 1}}
};

struct master {
    int n, retCnt;
    vvi board;
    int figureDir;

    master(vvi board) : board(board), n(board.size()), retCnt{} {}

    bool isValid(int y, int x) {
        return y >= 0 && y < n && x >= 0 && x < n;
    }

    bool isPossible(int y, int x) {
        int curValue = board[y][x];
        figureDir = -1;
        for (int i = 0; i < 5; i++) {
            bool flag = true;
            for (int j = 0; j < 4; j++) {
                int ny = y + figure[i][j][0];
                int nx = x + figure[i][j][1];
                if (!isValid(ny, nx) || board[ny][nx] != curValue) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                figureDir = i;
                bool flag2 = true;
                //검은 도형을 두는 것이 가능한지 불가능하다면 탐색종료
                for (int i = 4; i < 6; i++) {
                    int ny = y + figure[figureDir][i][0];
                    int nx = x + figure[figureDir][i][1];
                    if (!isValid(ny, nx) || board[ny][nx] != 0) {
                        flag2 = false;
                        break;
                    }
                    //x축값 위에 도형이 막힐수 있는 경우 탐색
                    for(int k = ny; k >= 0; k--){
                        if(board[k][nx] != 0){
                            flag2 = false;
                            break;
                        }
                    }
                    if(flag2 == false)
                        break;
                }
                if(flag2 == true)
                    return true;
            }
        }
        return false;
    }

    void simulation() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 0)
                    continue;
                if (isPossible(i, j)) {
                    retCnt++;
                    auto erase = [&](int y, int x, int dir) {
                        for (int i = 0; i < 4; i++) {
                            int ny = y + figure[dir][i][0];
                            int nx = x + figure[dir][i][1];
                            board[ny][nx] = 0;
                        }
                    };
                    erase(i, j, figureDir);
                    j = -1;
                }
            }
        }
    }
};

int solution(vector<vector<int>> board) {
    int answer = 0;
    master op(board);
    op.simulation();
    answer = op.retCnt;
    return answer;
}

int main() {
    vvi board = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                 {0, 0, 0, 0, 0, 0, 4, 0, 0, 0},
                 {0, 0, 0, 0, 0, 4, 4, 0, 0, 0},
                 {0, 0, 0, 0, 3, 0, 4, 0, 0, 0},
                 {0, 0, 0, 2, 3, 0, 0, 0, 5, 5},
                 {1, 2, 2, 2, 3, 3, 0, 0, 0, 5},
                 {1, 1, 1, 0, 0, 0, 0, 0, 0, 5}};
    cout << solution(board) << "\n";
}

---