2021 카카오 블라인드 채용 - 프로그래머스

https://school.programmers.co.kr/learn/challenges?order=recent&partIds=20069 

코딩테스트 연습 | 프로그래머스 스쿨

1. 신규 아이디 추천

• 특징: 문자열 처리 
• 어려웠던 부분: 문자열(string str)을 순회하면서, 조건에 맞으면 erase하는 함수를 사용했는데, erase함수 사용시, str.size()변화가 있어서 이부분을 처리하는 게 까다로웠다. 
• 구현방법: 열심히 구현
• 찾아본 함수
  • string erase: erase(지우려는 문자열의 첫번째 index, 몇개 지울건지)
  • string tolower: tolower(char) 
  • string substr: substr(자르려는 string의 첫번째 index, 몇개 자를 건지)
  • string replace: replace(교체하려는 문자열의 첫번쨰 index, 몇개까지 교체할 것인지, 교체 문자열)
• 코드

#include <bits/stdc++.h>

using namespace std;

string solution(string new_id) {
    string answer = "";
    
    string str;
    
    for(int i = 0; i< new_id.size(); i++)
    {
        str += tolower(new_id[i]);
    }

    for(int i = 0; i< str.size();)
    {
        if((str[i] >= 'a' && str[i] <= 'z') || str[i] == '-' || str[i] == '_' || str[i] == '.' ||isdigit(str[i]))
        {
            i++;
            continue;
        }
        else
        {
            str.erase(i, 1);
        }
        
    }

    int count = 0;
    for(int i = 0; i< str.size(); )
    {
        if(str[i] == '.') 
        {
            count++;
            i++;
        }
        else
        {
            if(count > 0) 
            {
                str.replace(i-count, count, ".");
                i = i-count;
            }
            i++;
            count = 0;
        }
    }
    if(count > 0) 
    {
        str.replace(str.size() - count, count, ".");

    }

    
    if(str.size() > 0) 
    {
        if(str[0] == '.') str.erase(0, 1);
        if(str[str.size()-1] == '.') str.erase(str.size()-1, 1);
    }
    
    if(str.size() == 0)
    {
        str+="a";
    }

    if(str.size() >= 16)
    {
        str = str.substr(0, 15);
    }
    if(str.size() == 15 && str[14] == '.') str.erase(14, 1);
    
    char t = str[str.size()-1];
    string t1;
    t1 += t;
    while(str.size() < 3)
    {
        str += t1;
    }
    
    answer = str;
    return answer;
}

 

2. 메뉴 리뉴얼

• 특징: dfs,  map
• 어려웠던 부분: dfs를 사용할 때 조건이 두가지 있었는데, 흔한 조건이지만 간만에 구현하려니 까다로웠다. 
  • 방문한 곳은 방문하지 않기 (아래 예시에서 x 표시) -> vis배열을 사용하여 구현
    • acde에서 dfs로 두개 뽑을 때: aa(x), ac, ad, ae, cc(x), cd, ... 
  • 자기보다 앞에있는 문자열은 접근하지 않기 (아래 예시에서 x 표시) -> dfs의 매개변수로 현재 넣은 char의 index를 prev 값으로 전달하고, 이 값을 순회할 때 i 값으로 설정
    • acde에서 dfs로 두개 뽑을 때: ac, ad, ae, ca(x), cd, ce, da(x), dc(x), de
• 구현방법
  • 2중 for문으로 courses(i), orders(j)를 순회
  • orders의 인자들을 sort하고, dfs(cur, orders[j], course[i], prev)을 호출 
    • orders의 인자들을 sort하지 않으면, map에 저장할 string이 중복될 수 있음 ex) CAD, ABC 두개의 string에서 2개씩 뽑는 dfs를 진행할 때, sort를 안하면 맵에 키값이 CA 와 AC가 저장되고 값이 각각 1이됨. sort를하면 키 AC, 값 2
  • dfs에서 string값인 orders[j]에서 int값인 course[i]개 만큼 문자열을 뽑음 
  • 탈출조건(cur == course[i])이 되면, 해당 문자열을 map에서 찾거나 생성하고, 그 값을 1 증가시킴
  • dfs가 끝나면, map을 순회하며 키의 값이 max가 되는 수를 찾음
  • map을 다시 순회하며, 값이 max가 되는 키를 찾아 answer에 저장함
• 찾아본 함수
  • string erase: erase(지우려는 문자열의 첫번째 index, 몇개 지울건지)
  • string tolower: tolower(char) 
  • string substr: substr(자르려는 string의 첫번째 index, 몇개 자를 건지)
  • string replace: replace(교체하려는 문자열의 첫번쨰 index, 몇개까지 교체할 것인지, 교체 문자열)
• 코드

#include <bits/stdc++.h>

using namespace std;

string ans[12];
map<string, int> m;
int vis[22];
int mx;
void dfs(int cur, string order, int course, int prev)
{
    if(cur == course)
    {
        string tmp = "";
        for(int i = 0; i < cur; i++)
        {
            tmp += ans[i];
        } 
        m[tmp]++;   
        return;
    }
    
    for(int i = prev; i < order.size(); i++)
    {
        if(vis[i] != 0) continue;
        vis[i] = 1;
        ans[cur] = order[i];
        prev = i;
        dfs(cur+1, order, course, prev);
        vis[i] = 0;
    }

}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    for(int i = 0; i< course.size(); i++)
    {
        int cur_course = course[i];
        
        for(int j = 0; j < orders.size(); j++)
        {
            fill(vis, vis+21, 0);
            mx = 0;
            sort(orders[j].begin(), orders[j].end());
            dfs(0, orders[j], cur_course, 0);
        }
        
        for(auto e : m) 
        { 
            mx = max(mx, e.second);
        }

        for(auto e : m) 
        {
            if(e.second == mx && mx > 1)
            {

                answer.push_back(e.first);
            }
        }
        
        m.clear();
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

3. 순위 검색

• 특징: 4차원 배열, dfs
• 어려웠던 부분: query에 '-'가 들어올 때 4차원 배열에서 어떻게 처리해줘야 할 지 고민하느라 시간이 오래걸렸다. '-'가 들어온 파트는 가능한 부분을 모두 고려해주어야 하니 dfs로 조합을 만들어 해결할 수 있다. 
• 구현방법
  • 4차원 배열을 설정함 
    • vector<int> a[3][2][2][2]; //언어/직군/경력/소울푸드
  • info를 순회하며, 해당 info의 배열의 벡터에 score를 push_back함. 
    • java, backend, junior, pizza, 200 이면 a[0][0][0][0].push_back(200);
  • 4중 for문을 돌며, a[i][j][k][p] 벡터의 값을 오름차순으로 sort함.
    • java, backend, junior, pizza인 사람들의 점수가 200, 100, 400일때 100 200 400으로 정렬
  • query를 순회하며, 질문 정보를 받아와서 각각의 변수(x, y, z, w, 기준 점수)를 설정함. '-'이면 -1로 설정 
    • java, backend, junior, pizza이면 int x = 0, int y = 0, int z = 0, int w = 0
    • cpp, frontend, senoir, chicken 이면 int x = 2, int y = 1, int z = 1, int w = 1
    • -, backend, junior, pizza이면 int x = -1, int y = 0, int z = 0, int w = 0
  • vector<int> xa, ya, za, wa 벡터를 만들어 x, y, z, w 값을 각각 push_back한다. 
    • 만약 x값이 -1이면, xa벡터에 0, 1, 2 를 push_back한다
    • 만약 y, z, w값이 -1이면, 각 벡터에 0, 1를 push_back한다
  • dfs를 돌면서, xa, ya, za, wa 벡터에 있는 값들로 조합을 만든다. 
    • x = -1, y = 0, z = 0, w = 0이면, xa = {0, 1, 2}, ya = {0}, za = {0}, wa = {0} 으로 3가지 조합이 나온다
    • dfs에서 탈출할때(재귀를 4번 호출해서, cx cy cz cw를 설정하면), a[cx][cy][cz][cw]를 순회(i)하면서 값이 기준 점수보다 커지면, 정답을 나타내는 ans 변수에 +=  a[cx][cy][cz][cw].size() - i하고 break; 해줌. *sort를 안하고, 순회하면서 ans를 1씩 증가시키는 방법은 시간 초과남.
      •  a[cx][cy][cz][cw] = (100, 200, 400) 이고, 200이상인 값을 찾는다고 하면, 전체 사이즈에서 - i 연산을 하여, 기준점수 이상인 값이 몇개인지 가져올 수 있다 
• 코드

#include <bits/stdc++.h>

using namespace std;
vector<int> a[3][2][2][2]; //언어/직군/경력/소울푸드
vector<int> xa;
vector<int> ya;
vector<int> za;
vector<int> wa;
int ans;
int certainscore;
int res[4];
vector<string> split(string& str)
{
    string tmp = "";
    vector<string> ret;
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == ' ')
        {
            ret.push_back(tmp);
            tmp = "";
        }
        else
        {
            tmp += str[i];

        }
    }
    ret.push_back(tmp);
    return ret;
}

void dfs(int cur)
{
    if(cur == 4)
    {
        int cx = res[0];  int cy = res[1];  int cz = res[2];  int cw = res[3];
        
        //a[cx][cy][cz][cw]가 오름차순 정렬                                                               
        int totalcnt =  a[cx][cy][cz][cw].end() - lower_bound(a[cx][cy][cz][cw].begin(), a[cx][cy][cz][cw].end(), certainscore);
        ans+= totalcnt;
        
        return;
    }
    
    if(cur == 0)
    {
        for(int i = 0; i < xa.size(); i++)
        {
            res[cur] = xa[i];
            dfs(cur+1);
        }
    }
    if(cur == 1)
    {
        for(int i = 0; i < ya.size(); i++)
        {
            res[cur] = ya[i];
            dfs(cur+1);
        }
    }
    if(cur == 2)
    {
        for(int i = 0; i < za.size(); i++)
        {
            res[cur] = za[i];
            dfs(cur+1);
        }
    }
    
    if(cur == 3)
    {
        for(int i = 0; i < wa.size(); i++)
        {
            res[cur] = wa[i];
            dfs(cur+1);
        }
    }
    
}
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    for(int i = 0; i < info.size(); i++)
    {
        vector<string> vec = split(info[i]);
        int x,y,z,w;
        if(vec[0] == "java") x = 0;
        else if(vec[0] == "python") x = 1;
        else x = 2;
        
        if(vec[1] == "backend") y = 0;
        else y = 1;
        
        if(vec[2] == "junior") z = 0;
        else z = 1;
        
        if(vec[3] == "pizza") w = 0;
        else w = 1;
        
        int score = stoi(vec[4]);
        
        a[x][y][z][w].push_back(score);
    }
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                for(int p = 0; p < 2; p++)
                {
                    sort(a[i][j][k][p].begin(), a[i][j][k][p].end());
                }
            }
        }
    }
    
    for(int i = 0; i < query.size(); i++)
    {
        vector<string> vec = split(query[i]);
        xa.clear(); ya.clear(); za.clear(); wa.clear();
        ans = 0;
        int x = -1; int y = -1; int z = -1; int w = -1;
        if(vec[0] == "java") x = 0;
        else if(vec[0] == "python") x = 1;
        else if (vec[0] == "cpp") x = 2;
        else
        {
            x = -1;
        }
        
        if(vec[2] == "backend") y = 0;
        else if(vec[2] == "frontend") y = 1;
        else
        {
            y = -1;
        }
        
        if(vec[4] == "junior") z = 0;
        else if(vec[4] == "senior") z = 1;
        else 
        {
            z = -1;
        }
        
        if(vec[6] == "pizza") w = 0;
        else if(vec[6] == "chicken") w = 1;
        else 
        {
            w = -1;
        }
        
        certainscore = stoi(vec[7]);

        if(x == -1) {xa.push_back(0); xa.push_back(1); xa.push_back(2); }
        else xa.push_back(x); 
        if(y == -1) {ya.push_back(0); ya.push_back(1); }
        else ya.push_back(y); 
        if(z == -1) {za.push_back(0); za.push_back(1); }
        else za.push_back(z); 
        if(w == -1) {wa.push_back(0); wa.push_back(1); }
        else wa.push_back(w);
        
        dfs(0);
        answer.push_back(ans);
        
    }
    
    return answer;
}

 

4. 합승 택시 요금

• 특징: 다익스트라 
• 어려웠던 부분: 문제를 읽고, 아이디어가 바로 안떠올랐다.
  • 한참 생각하다, s에서 s제외 다른 모든 노드로 가는 최솟값을 구하고(동행), 그 노드에서 a, b로 가는 최소값(따로)을 구해서 더해서 ans배열에 저장. ans배열을 순회하면서 최솟값을 찾으면 될거같다고 생각했다. 
  • 대놓고 다익스트라 문제인데, 내가 다익스트라 문제가 익숙하지 않아서 아이디어를 떠올리는데 시간이 걸렸다고 생각한다. 
• 구현방법
  • 시작노드에서 다익스트라 알고리즘(우선순위큐 이용)
  • 시작노드 제외한 모든 노드에서 다익스트라 알고리즘, a와 b에 들어있는 거리를 가져옴.
• 코드

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> adj[202]; 
int todist[202];
int dist[202];
int ans[202];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    for(int i = 0; i < fares.size(); i++)
    {
        int st = fares[i][0]; int en = fares[i][1]; int w = fares[i][2];
        adj[st].push_back(make_pair(w, en));
        adj[en].push_back(make_pair(w, st));
    }
    fill(todist, todist+n+1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 

    todist[s] = 0;
    pq.push(make_pair(todist[s], s));
    while(!pq.empty())
    {
        auto cur = pq.top(); pq.pop();
        if(todist[cur.second]!=cur.first) continue; 
        for(auto nxt: adj[cur.second])
        {
            if(todist[nxt.second] <= todist[cur.second]+nxt.first) continue;
            todist[nxt.second] = todist[cur.second]+nxt.first;
            pq.push(make_pair(todist[nxt.second], nxt.second));
        }
    }    
    
    int mn = INT_MAX;
    for(int i = 1; i < n+1; i++)
    {
        
        fill(dist, dist+n+1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        dist[i] = 0;
        pq.push(make_pair(dist[i], i));
        while(!pq.empty())
        {
            auto cur = pq.top(); pq.pop();
            if(dist[cur.second]!=cur.first) continue; 
            for(auto nxt: adj[cur.second])
            {
                if(dist[nxt.second] <= dist[cur.second]+nxt.first) continue;
                dist[nxt.second] = dist[cur.second]+nxt.first;
                pq.push(make_pair(dist[nxt.second], nxt.second));
            }
        }
        ans[i] = todist[i] + dist[a] + dist[b];
        mn = min(mn, ans[i]);   
    }
    answer = mn;
   
    return answer;
}