2020 카카오 인턴십 코딩테스트 혼내주기

며칠전에 카카오 2021 여름 인턴십 공고가 올라와서 작년 문제를 실전처럼 시간을 재고 풀어봤다. 결과는 4솔. 5번 문제는 감이 안잡혀서 공식 블로그 해설을 참고해 풀어봤다. 작년엔 서류와 코딩테스트를 함께 평가해서 그런지 3솔하고 붙은 사람도 있고 5문제를 풀고 떨어진 사람도 있는 것 같다. 

이번에는 코딩테스트를 붙고 서류를 제출하기 때문에 커트라인이 더 높을테니 5문제면 4~5문제를 풀어야 할 것 같다...

 

 

 

풀이

1번 키패드 누르기
그냥 풀면 된다. 나머지 연산으로 손을 정했는데 0일때를 처리 안해줘서 잠깐 헤맸다.

#include <string>
#include <vector>

using namespace std;

pair<int ,int> getGrid(int num) {
    if(num == 0) return make_pair(3, 1);
    int x = (num-1) / 3;
    int y = (num-1) % 3;
    
    return make_pair(x, y);
}

int getDist(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    pair<int, int> left = make_pair(3, 0);
    pair<int, int> right = make_pair(3, 2);

    for(int num : numbers) {
        // left
        if(num%3 == 1) {
            left = getGrid(num);
            answer += 'L';
        }
        // right
        else if(num != 0 && num%3 == 0) {
            right = getGrid(num);
            answer += 'R';
        }
        else {
            pair<int, int> cp = getGrid(num);
            int ld = getDist(left, cp);
            int rd = getDist(right, cp);
            if(ld > rd) {
                right = cp;
                answer += 'R';
            }
            else if(ld < rd) {
                left = cp;
                answer += 'L';
            }
            else {
                if(hand == "right") {
                    right = cp;
                    answer += 'R';
                } else {
                    left = cp;
                    answer += 'L';
                }
            }
        }
    }

    return answer;
}

 

 

2번 수식 최대화
딱 보고 쉬운데 문자열 처리할 생각하니 막막해서 마지막에 풀었다. 나는 숫자와 연산자들을 각각의 링크드 리스트에 저장하고, 연산자 우선순위를 dfs로 정했다. 순위가 높은 연산자부터 (num op num)을 링크드 리스트에서 뽑아서 계산하고, 다시 넣어서 최종적으로 남는 숫자가 그 우선순위 수식 값이 되도록 했다.

풀고 보니 생각보다 문자열 처리가 복잡한 문제는 아니었고, 경우의 수가 6개밖에 되지 않기 때문에 그냥 우선순위를 미리 적어놓고 하는게 더 나았을 것 같다.

#include <vector>
#include <algorithm>
#include <list>

using namespace std;

list<long long> numbers;
list<char> operators;
char op[3] = {'+', '-', '*'};  // + - *
bool visited[3];
int order[3];

long long ans = 0;

long long calculate(long long n1, long long n2, char oper) {
    if(oper == '+') return n1 + n2;
    else if(oper == '-') return n1 - n2;
    else return n1 * n2;
}

void d(int cnt) {
    if(cnt == 3) {
        // 계산
        list<long long> nums(numbers);
        list<char> ops(operators);
        for(int i = 0; i < 3; ++i){

            list<long long>::iterator nit = nums.begin();
            list<char>::iterator oit = ops.begin();

            for(; oit != ops.end(); ++nit, ++oit) {
                while(*oit == op[order[i]]) {
                    long long n1 = *nit; nit = nums.erase(nit);
                    long long res = calculate(n1, *nit, *oit);
                    *nit = res;
                    oit = ops.erase(oit);
                }
            }
        }
        ans = max(ans, abs(*nums.begin()));
        
        return ;
    }

    for(int i = 0; i < 3; ++i){
        if(visited[i]) continue;
        order[cnt] = i;
        visited[i] = true;
        d(cnt+1);
        visited[i] = false;
    }
}

long long solution(string expression) {
    long long answer = 0;

    string buf;
    for(char c : expression) {
        if(c == '-' || c == '+' || c == '*') {
            numbers.push_back(stol(buf));
            buf = "";
            operators.push_back(c);
        }
        else {
            buf += c;
        }
    }
    numbers.push_back(stol(buf));

    d(0);
    
    answer = ans;
    return answer;
}

 

 

3번 보석 쇼핑
투 포인터 문제. 공부하길 잘했다!!
먼저 unordered_map으로 보석의 목록을 만들어주고 투 포인터로 모든 보석을 포함하는 구간 중 길이가 가장 짧은 구간을 찾으면 된다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string, int> map;
    int idx = 0;
    for(string s : gems) {
        if(map.find(s) == map.end()){
            map[s] = idx++;
        }
    }
    int sze = gems.size();
    vector<int> cnt(idx, 0); 
    int s = 0, e = 0, kind = 0, ansS = 0, ansE = 0, len = 1e9;
    while(1) {
        if(kind >= idx) {
            cnt[map[gems[s]]]--;
            if(cnt[map[gems[s]]] == 0) kind--;
            s++;
        }
        else if(e >= sze) break;
        else {
            cnt[map[gems[e]]]++;
            if(cnt[map[gems[e]]] == 1) kind++;
            e++;
        }

        if(kind == idx && len > (e-s)){
            ansS = s; ansE = e;
            len = e-s;
        }

    }
    answer.push_back(ansS+1);
    answer.push_back(ansE);
    
    return answer;
}

 

 

4번 경주로 건설
그냥 다잌스트라로 풀었다. 근데 이 부분에서 +500을 안해줘서 좀 헤맸다.

if(board[nx][ny] == 1 || map[nx][ny]+500 <= nDist) continue;

현재까지 거리가 더 가까워도, 직선 도로인지 코너인지에 따라 다음 비용이 변하기 때문에 낭낭하게 +500이하로 차이나는 친구들을 우큐에 넣어주면 된다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct point{
    int x, y, dist, direction;
    point(int a, int b, int c, int d) {x = a, y=b, dist=c, direction=d;}
    bool operator<(const point &p) const{
        return dist > p.dist;
    }
};

int solution(vector<vector<int>> board) {

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int answer = 0;

    int n = board[0].size();
    int map[n][n];
    memset(map, 0x7f, sizeof(map));

    priority_queue<point> pq;
    pq.push(point(0, 0, -500, -1));
    map[0][0] = 0;

    while(!pq.empty()) {
        point cp = pq.top(); pq.pop();
        if(cp.x == n-1 && cp.y == n-1) {
            answer = cp.dist;
            break;
        }
        
        for(int i = 0; i < 4; ++i){ // down right up left
            int nx = cp.x + dx[i], ny = cp.y + dy[i], nDist = cp.dist + 100;
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(cp.direction != i) nDist += 500;
            if(board[nx][ny] == 1 || map[nx][ny]+500 <= nDist) continue;
            map[nx][ny] = nDist;
            pq.push(point(nx, ny, nDist, i));
        }
    }

    return answer;
}

 

 

5번 동굴 탐험
이 문제는 풀지 못해서 공식 블로그 풀이를 보고 내가 생각하기 가장 편한 방법으로 풀었다.
먼저 path 벡터로 adjacency list를 만든 뒤, 0부터 시작해서 모든 노드들의 부모 노드를 저장한다. 이후 order 벡터에서 나오는 순서관계에 따라 부모에 추가한다. 이렇게 하면 모든 노드의 parent (현재 노드를 탐험하기 전 방문해야 하는 노드들)를 구할 수 있다.

이후 실제로 먼저 방문해야 하는 노드들을 방문할 수 있는지 확인한다. 먼저 노드의 상태를 -1 (진행중)로 두고, 노드를 확인한 뒤 (trace 함수), 확인이 완료되면 1로 바꿔준다. 만약 한 노드의 확인이 진행중인 상태에서 또 다른 진행중인 노드를 발견하면, 마치 deadlock과 같은 상태이므로 false를 리턴하고 모든 노드를 확인할 수 있다면 true를 리턴한다.

분명 맞게 풀었는데 30번째 tc가 틀려서 검색해보니 order에서 0보다 먼저 방문하는 경우의 입력도 있다고 한다. 실제 코딩테스트에서 이 문제를 풀었어도 이 예외는 절대 못잡았을 것 같다...

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

vector<int> adj[200000];
vector<int> parent[200000];

bool visited[200000];

void makeTree(int n) {
    visited[n] = true;
    for(int child : adj[n]) {
        if(visited[child]) continue;
        parent[child].push_back(n);
        makeTree(child);
    }
}

// 0 x discovered
// 1 done
// -1 ongoing
int status[200000];

bool trace(int n) {
    for(int p : parent[n]) {
        if(status[p] == 1) continue;
        if(status[p] == -1) return false;
        status[p] = -1;
        if(trace(p) == false) return false;
        status[p] = 1;
    }
    return true;
}

bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    bool answer = true;

    for(vector<int> v : path) {
        adj[v[0]].push_back(v[1]);
        adj[v[1]].push_back(v[0]);
    }

    for(vector<int> v : order) {
        parent[v[1]].push_back(v[0]);
    }

    // TC 30
    if(!parent[0].empty()) return false;

    makeTree(0);

    status[0] = 1;
    for(vector<int> v : order) {
        if(trace(v[1]) == false) return false;
    }

    return answer;
}

 

 

실제 코딩테스트에서도 마찬가지인거로 아는데, 카카오는 모든 TC를 줘서 혹시나 놓친 예외를 생각하지 않아 맘이 편하다. 블라인드 코딩테스트 보다는 쉬우니 통과했으면 좋겠다.