2022 카카오 테크인턴십 코딩테스트 후기

전날 작년 테크인턴십 문제를 모두 풀어보았고, 생각보다 난이도가 높게 나와서 긴장을 좀 한 상태였다. 체감 난이도는 작년보다 약간 쉽거나 비슷한 것 같다.

그것보다도 백준스타일에 익숙해져 있어서 파라미터로 받아서 넘기는 프로그래머스 스타일로 짜면 코드가 많이 길어져 힘들어지는 경향이 있다.

5번 충분히 풀만 했는데 못 푼게 좀 아쉽다. 

 

결과적으로 최종 면접에서 떨어졌다. 서류 준비며 면접 준비며 아무것도 안 되어 있던터라 기대없이 봤기 때문에 타격은 없는데, 앞으로 어떻게 준비해야할 지 감을 많이 잡을 수 있었다.

1시간동안 질문할 거리 어떻게든 찾아내신 면접관님들께 박수

 

1번

MBTI같이 성향에 대한 응답이 주어지고, 성향에 대한 결과를 리턴하는 문제.

단순 구현문제라 따로 언급할 것은 없는다. 다만, 처음에 string 들어오길래 map갈겼는데 char형으로 처리해줬기 때문에 그냥 배열로 처리했어도 됐다는 점.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 10005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

string solution(vector<string> survey, vector<int> choices) {
    string answer = "";

    int n = survey.size();
    map<char, int> score;
    score['R'] = 0;
    score['C'] = 0;
    score['J'] = 0;
    score['A'] = 0;
    for (int i = 0; i < n; ++i) {
        if (survey[i][0] > survey[i][1]) {
            swap(survey[i][0], survey[i][1]);
            choices[i] = 8 - choices[i];
        }
        score[survey[i][0]] += 4 - choices[i];
    }

    if (score['R'] >= 0) answer.push_back('R'); else answer.push_back('T');
    if (score['C'] >= 0) answer.push_back('C'); else answer.push_back('F');
    if (score['J'] >= 0) answer.push_back('J'); else answer.push_back('M');
    if (score['A'] >= 0) answer.push_back('A'); else answer.push_back('N');

    return answer;
}

#ifndef ONLINE_JUDGE
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    

    return 0;
}
#endif

 

2번

queue가 2개 주어지는데, 하나의 queue에서 pop후 다른 queue에 push하는 연산을 할 수 있다. 이 연산으로 두 queue안에 있는 값의 합이 같도록 만들려고 할 때 위 연산의 최소 횟수를 구하는 문제.

 

두 queue를 붙혀서 하나의 배열로 만들어주고 슬라이딩 윈도우(또는 투포인터)로 queue의 합이 sum의 절반이 되는 지점을 찾아서 최소 연산 횟수를 update하면 된다. 두 queue를 붙히는 순서에 따라서 답이 달라질 수 있으므로 2번 해주면 된다.

생각보다 많이 고전했는데, 슬라이딩 윈도우를 할 때 l, r의 위치에 따라서 queue의 연산횟수 계산 방법이 달라진다. 크게 3개 케이스가 있는데, 엣지케이스 하나가 있어서 총 4개 케이스로 분리해줘야한다. 이거 때문에 3~4개 tc를 틀렸었고, 3번문제를 푼 뒤에 다시 생각해서 풀었다.

 

조금 생각해봤는데 굳이 배열 하나를 만들 필요가 없을 것 같다. queue의 합이 sum이 절반이 되도록 계속 연산을 하면 된다. 어차피 연산은 최대 두 queue의 크기의 합만큼만 돌리면 되므로 시간내로 돌릴 수 있다. 이렇게 구현했으면 케이스 분류할 필요없이 깔끔하게 구현이 가능했어서 조금 아쉽다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 10005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int solution(vector<int> queue1, vector<int> queue2) {
    int answer = INF;

    ll sum = 0;
    for (int e : queue1) {
        sum += e;
    }
    for (int e : queue2) {
        sum += e;
    }
    if (sum % 2 == 0) {
        vector<int> arr(queue1);
        for (int e : queue2) {
            arr.emplace_back(e);
        }

        int n = arr.size();
        ll psum = 0;
        int l = 0;
        for (int i = 0; i < n; ++i) {
            psum += arr[i];
            while (psum > sum / 2) {
                psum -= arr[l];
                ++l;
            }
            if (psum == sum / 2) {
                if (i == n - 1 && l >= n / 2) {
                    answer = min(answer, l - n / 2);
                }
                else if (l < n / 2 && i < n / 2) {
                    answer = min(answer, i + 1 + n / 2 + l);
                } else if (l < n / 2 && i >= n / 2) {
                    answer = min(answer, l + i + 1 - n / 2);
                } else {
                    answer = min(answer, i + 1 - n / 2 + n / 2 + l - n / 2);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            if (i < n / 2) {
                arr[i] = queue2[i];
            } else {
                arr[i] = queue1[i - n / 2];
            }
        }

        psum = 0;
        l = 0;
        for (int i = 0; i < n; ++i) {
            psum += arr[i];
            while (psum > sum / 2) {
                psum -= arr[l];
                ++l;
            }
            if (psum == sum / 2) {
                if (i == n - 1 && l >= n / 2) {
                    answer = min(answer, l - n / 2);
                }
                else if (l < n / 2 && i < n / 2) {
                    answer = min(answer, i + 1 + n / 2 + l);
                } else if (l < n / 2 && i >= n / 2) {
                    answer = min(answer, l + i + 1 - n / 2);
                } else {
                    answer = min(answer, i + 1 - n / 2 + n / 2 + l - n / 2);
                }
            }
        }
    }

    return answer == INF ? -1 : answer;
}

#ifndef ONLINE_JUDGE
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    

    return 0;
}
#endif

 

3번

능력치가 2가지가 있고, 초기 두 능력치가 주어진다. 하나의 능력치를 1올릴 때 마다 하루씩 소요된다. 또한, 임무가 주어지는데 임무를 시작하기 위한 초기 조건과, 임무 완수시 얻는 두 능력치의 양, 임무에 소요되는 시간이 주어진다. 이때, 모든 임무를 수행하기 위한 능력치를 갖추는데 드는 최소 일 수를 구하는 문제.

 

모든 임무를 수행하는데 필요한 능력치를 갖추는게 목적이지, 모든 문제를 풀 필요는 없다. 처음에는 두 능력치를 인덱스로하는 dp를 생각했었다. 뭐 사실 다익스트라도 dp의 일종이긴 하지만 어쨋든 결론적으론 다익스트라로 풀었고, 빠른 구현을 위해(vscode에서 priority_queue 선언시 pair를 사용하면 엄청 렉이 먹는다) spfa로 구현했다.

중간중간 이슈가 많았는데, 특히 현재 능력치가 150을 넘어가면 그냥 150으로 고정시켜줘야 했었다. 예를 들어 임무 중 능력치1을 1올려주고 2를 150올려주는 임무가 있을 때 이 임무를 150번 수행하면 능력치2가 150150이 되므로 테이블크기를 [150150][150*150]으로 해줘야하기 때문에 메모리가 터진다. 능력치를 상한선인 150으로 맞춰주면 문제해결이 가능하다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 200
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

queue<pii> q;
bool isIn[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];

int bfs(int alp, int cop, int targetAlp, int targetCop, const vector<vector<int>>& problems) {
    for (int i = 0; i < MAX_N; ++i)
        fill_n(dist[i], MAX_N, INF);

    q.emplace(alp, cop);
    isIn[alp][cop] = true;
    dist[alp][cop] = 0;

    int res = INF;
    while (q.size()) {
        int ha = q.front().first;
        int hp = q.front().second;
        q.pop();
        isIn[ha][hp] = false;

        if (ha >= targetAlp && hp >= targetCop) {
            res = min(res, dist[ha][hp]);
            continue;
        }

        for (int i = 0; i < problems.size(); ++i) {
            if (problems[i][0] <= ha && problems[i][1] <= hp) {
                int na = min(ha + problems[i][2], targetAlp);
                int np = min(hp + problems[i][3], targetCop);
                int nxtCost = dist[ha][hp] + problems[i][4];

                if (dist[na][np] > nxtCost) {
                    dist[na][np] = nxtCost;
                    if (isIn[na][np] == false) {
                        q.emplace(na, np);
                        isIn[na][np] = true;
                    }
                }
            }
        }

        int na = min(ha + 1, targetAlp);
        int np = min(hp, targetCop);
        int nxtCost = dist[ha][hp] + 1;
        if (dist[na][np] > nxtCost) {
            dist[na][np] = nxtCost;
            if (isIn[na][np] == false) {
                q.emplace(na, np);
                isIn[na][np] = true;
            }
        }

        na = min(ha, targetAlp);
        np = min(hp + 1, targetCop);
        nxtCost = dist[ha][hp] + 1;
        if (dist[na][np] > nxtCost) {
            dist[na][np] = nxtCost;
            if (isIn[na][np] == false) {
                q.emplace(na, np);
                isIn[na][np] = true;
            }
        }
    }
    return res;
}

int solution(int alp, int cop, vector<vector<int>> problems) {
    int answer = 0;

    int targetAlp = 0;
    int targetCop = 0;
    for (auto& problem : problems) {
        targetAlp = max(targetAlp, problem[0]);
        targetCop = max(targetCop, problem[1]);
    }

    answer = bfs(alp, cop, targetAlp, targetCop, problems);

    return answer;
}

#ifndef ONLINE_JUDGE
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cout << solution(1050, 1500, {{150,150,1,1,100}, {0,0,3,150,1}}) << endl;

    return 0;
}
#endif

 

4번

그래프로 표현되는 산을 등산하려 하는데, vertex는 등산로의 입구들과 쉼터, 정상지점들로 구성된다. 입구를 통해 입산하여 쉼터들을 거쳐서 정상지점들 중 하나에 도착한 뒤 내려와야한다. 반드시 들어간 입구를 통해 산에서 나와야하며, 한번의 등산에서 여러번의 정상지점을 들리면 안 된다. 즉, 경로에는 반드시 하나의 정상지점과 두 개의 같은 입,출구가 있어야한다. 등산코스의 총 cost는 edge의 cost중 max값으로 결정된다. 이때, 등산코스의 최소 cost와 그 코스에서 들르게 되는 정상지점을 구하는 문제.

 

작년 코테에서 tree위에서 parametric과 greedy가 섞인 문제가 나왔는데, 그걸 어제 봐서 그런지 보자마자 parametric으로 생각했다. 결정함수를 생각하는 과정에서 mid보다 큰 cost의 edge를 무시해주면서 찾아줘야겠다~ 하고 생각했는데 이 생각을 확장하다보니 MST생각이 났다. 바로 유레카 외치고 union-find부터 구현하고 있었는데, MST로만으로는 구현이 불가능할 것 같아서 bfs를 추가했다.

 

실제로는 여러 케이스를 나눠줬었지만, 가장 general한 케이스로 위와 같은 케이스를 생각했다. 반약 어떤 componet에 여러 정상지점(빨간색)이 있고, 이들과 연결된 쉼터(하얀색)이 있다고 하자. 이때 비슷한 구조로 입구들(파란색)과 연결된 쉼터(하얀색)이 정상지점 component에 연결되게 된다면 이 상태만으로는 어느 지점이 정상지점이 될 수 있는지 판단할 수가 없다.

 

그래서 빨간 component에 파란 component가 연결되는 순간, 파란 component쪽에서 bfs를 돌려서 가장 먼저 발견하는 정상지점을 구해줬다. 어차피 cost를 기준으로 edge들을 정렬해서 하나씩 추가해줬기 때문에 가장 먼저 만나는 정상지점까지의 거리는 구해준 것이기 때문에 bfs로 정상지점의 번호만 받아오면 된다.

tc들 중에서 2개정도가 800ms로 많이 밀렸었는데, 같은 cost로 갈 수 있는 정상지점이 여러개 있으면 가장 작은 정상지점 번호를 출력해야하기 때문에 bfs를 여러번 돌아주게 되고, 그 때문에 시간이 오래걸린 것같다. 사실 제출할 때에도 “모든 edge의 cost가 같으면 시간초과도 가능하겠는데?”싶었었는데 다행이 통과는 되었다. 사실 개선할 수 있었는데, 면접보게 될 경우 이 부분 개선할 수 있었을 것같다고 언급하기 위해서 아껴두었다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 50005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

struct Edge {
    int s, e, c;
};
bool operator> (const Edge& a, const Edge& b) {
    return a.c > b.c;
}

int parent[MAX_N];
int level[MAX_N];
int groupColor[MAX_N]; // 0: white, 1: red, 2: blue
bool isGate[MAX_N];
bool isSummit[MAX_N];
int find(int u) {
    if (parent[u] == u) {
        return u;
    }
    return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);

    if (u == v) {
        return;
    }
    if (level[u] > level[v]) {
        swap(u, v);
    }
    if (level[u] == level[v]) {
        ++level[v];
    }
    parent[u] = v;
    groupColor[u] = max(groupColor[u], groupColor[v]);
    groupColor[v] = groupColor[u];
}

vector<int> adj[MAX_N];
int bfs(int start) {
    queue<int> q;
    bool visited[MAX_N] = { false, };

    q.emplace(start);
    visited[start] = true;

    vector<int> candidates;
    while(q.size()) {
        int here = q.front();
        q.pop();

        if (isSummit[here])  {
            candidates.emplace_back(here);
            continue;
        }

        for (int nxt : adj[here]) {
            if (visited[nxt]) {
                continue;
            }
            q.emplace(nxt);
            visited[nxt] = true;
        }
    }
    return *min_element(all(candidates));
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for (int i = 0; i < MAX_N; ++i)
        parent[i] = i;
    priority_queue<Edge, vector<Edge>, greater<Edge>> edges;
    for (auto& path : paths) {
        edges.push({path[0], path[1], path[2]});
    }

    for (int summit : summits) {
        groupColor[summit] = 1;
        isSummit[summit] = true;
    }
    for (int gate : gates) {
        groupColor[gate] = 2;
        isGate[gate] = true;
    }
    

    int minValue = INF;
    int lastCost = 0;
    while(edges.size()) {
        Edge edge = edges.top();
        edges.pop();
        if (lastCost != edge.c && minValue != INF) {
            break;
        }
        lastCost = edge.c; 

        if (edge.s != edge.e) {
            adj[edge.s].emplace_back(edge.e);
            adj[edge.e].emplace_back(edge.s);
        }

        int s = find(edge.s);
        int e = find(edge.e);

        if (groupColor[s] == groupColor[e] || groupColor[s] == 0 || groupColor[e] == 0) {
            merge(s, e);
            continue;
        }

        if (groupColor[s] == 1) {
            minValue = min(minValue, bfs(edge.e));
        } else if (groupColor[e] == 1) {
            minValue = min(minValue, bfs(edge.s));
        }
    }
    vector<int> answer;
    answer.push_back(minValue);
    answer.push_back(lastCost);
    return answer;
}

#ifndef ONLINE_JUDGE
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    

    return 0;
}
#endif

 

5번

배열 전체를 1줄 내리는 연산과 제일 겉부분만 시계방향으로 돌리는 두 연산이 쿼리로 들어올 때 최종 배열을 출력하는 문제.

문제 description은 간단한데 생각보다 많이 어려웠다. 그냥 2중 deque로 구현하면 배열을 전체 1줄 내리는 연산은 O(1)에 가능하다. 그리고 배열 겉부분 회전 시에도 row부분은 O(1)에 가능하고, column부분만 O(row)가 걸린다. 배열을 펴서 규칙찾아서 lazy세그가 되는지, 그냥 linkedlist로 깨작깨작하는건지, 인덱스 관리로 처리하는건지 여러 고민을 해봣는데, 결국 못 풀고 정확도 부분점수만 받고 넘겼다.

저녁 먹으면서 생각을 좀 해봤는데 deque만으로 구현 가능하다. 배열의 양 끝 column을 따로 deque로 떼어주고, 나머지 중간의 모든 row는 2중 deque로 관리하면 O(1)에 모두 처리가능하다.

배열 전체를 1줄 내리는 연산은 기존의 deque처리 + 양 옆 처리 deque를 pop + push, 시계방향으로 돌리는 연산은 deque를 pop_back, 그리고 pop한 값을 중간 deque에 pop_front 하는 식으로 구현가능하다. 충분히 생각 가능했는데 좀 아쉽다...

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifdef ONLINE_JUDGE
#define endl '\n'
#endif

#define all(x) x.begin(), x.end()
#define INF (INT_MAX / 2)
#define MAX_N 50005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int r;
int c;

void rotate(deque<deque<int>>& arr) {
    int temp = arr[0].back();
    arr[0].pop_back();
    arr[0].push_front(arr[1].front());
    for (int i = 0; i < r - 1; ++i) {
        arr[i][0] = arr[i + 1][0];
    }
    arr[r - 1].pop_front();
    arr[r - 1].push_back(arr[r - 2].back());
    for (int i = r - 1; i >= 1; --i) {
        arr[i][c - 1] = arr[i - 1][c - 1];
    }
    arr[1][c - 1] = temp;
}

void shiftRow(deque<deque<int>>& arr) { 
    arr.emplace_front(arr.back());
    arr.pop_back();
}

vector<vector<int>> solution(vector<vector<int>> rc, vector<string> operations) {
    r = rc.size();
    c = rc[0].size();
    deque<deque<int>> arr;
    for (vector<int>& t : rc){
        arr.push_back(deque<int>());
        for (int& e : t){
            arr.back().push_back(e);
        }
    }

    for (string& operation: operations) {
        if (operation.compare("Rotate") == 0) {
            rotate(arr);
        } else {
            shiftRow(arr);
        }
    }
    vector<vector<int>> answer;
    for (deque<int>& t : arr){
        answer.push_back(vector<int>());
        for (int& e : t){
            answer.back().push_back(e);
        }
    }
    return answer;
}

#ifndef ONLINE_JUDGE
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    

    return 0;
}
#endif