오늘 진행중인 2021 KAKAO BLIND RECRUITMENT 1차 코딩테스트에 참여하고 출제된 문제 7개에 대한 풀이를 남긴다. 물론, 해당 포스트는 대회가 끝나는 시간인 오후 7시 30분 이후에 포스트할 예정이다.
결과
군필 조건만 없었으면…
문제1.
신규 유저의 아이디가 담긴 string이 주어졌을 때 문제에서 주어진 규칙에 따라 문자열을 변형한 뒤 반환하는 문제이다.
풀이
해당 문제는 문제에서 주어진 7개 단계를 수행하는 함수를 하나 만들고 문자열이 더이상 바뀌지 않을 때까지 돌려주면 된다.
단순 구현문제이다.
#include <string>
#include <vector>
using namespace std;
string run(string new_id){
string step1 = "";
for(int j = 0; j < new_id.size(); ++j){
if(new_id[j] >= 'A' && new_id[j] <= 'Z')
step1 += new_id[j] - 'A' + 'a';
else step1 += new_id[j];
}
string step2 = "";
for(int j = 0; j < step1.size(); ++j){
if((step1[j] >= 'a' && step1[j] <= 'z') || (step1[j] >= '0' && step1[j] <= '9')
|| step1[j] == '-'
|| step1[j] == '_'
|| step1[j] == '.')
step2 += step1[j];
}
string step3 = "";
for(int j = 0; j < step2.size(); ++j){
if(j && step2[j] == '.' && step2[j - 1] == '.') continue;
step3 += step2[j];
}
string step4 = "";
for(int j = 0; j < step3.size(); ++j){
if(j == 0 && step3[j] == '.') continue;
if(j == step3.size() - 1 && step3[j] == '.') continue;
step4 += step3[j];
}
string step5 = "";
if(step4 == "") step5 += 'a';
else step5 = step4;
string step6 = "";
for(int j = 0; j < step5.size() && j < 15; ++j)
step6 += step5[j];
string step7 = step6;
while(step7.size() < 3){
step7 += step6.back();
}
return step7;
}
string solution(string new_id) {
string ans = new_id;
for(string tmp; ; ){
tmp = run(ans);
if(tmp != ans){
ans = tmp;
}else break;
}
return ans;
}
문제2.
서로다른 대문자 알파벳으로 이루어진 문자열이 담긴 배열 orders와 오름차순으로 정렬된 자연수가 담긴 배열 course가 주어진다. 이때 course에 있는 각 자연수의 길이에 해당하는 문자열을 구해야 하는데, 각 문자열이 가지고 있는 알파벳들이 orders배열에 있는 각 문자열에 모두 나타난 개수가 2이상이면서 현재 길이에 대해 최댓값을 가져야한다. 이러한 문자열들을 사전순으로 정렬하여 반환하는 문제다.
풀이
우선 course의 각 길이에 해당하는 문자열들을 구성해야 한다. 이는 DFS를 이용하여 서로다른 알파벳 대문자로 이루어진 문자열을 모든 조합에 대해 구성하도록 구현할 수 있다. 알파벳은 26가지 이고 course에 포함되는 최대 값은 10이므로 최대 $\sum_{r=1}^{10}\binom{26}{r}=10970271$ 가지의 문자열이 나온다.
이후 각 조합에 대해 orders배열을 돌며 조건을 만족하는 문자열들의 개수를 구하하고 개수가 최대인 문자열들을 찾으면 된다.
주어진 제한이 작다는 점에서 단순 구현문제이다.
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
struct strt{
string str;
int cnt;
};
vector<set<char>> O;
vector<strt> nn;
int nmax = -1;
int getCount(vector<char>& selected){
int ret = 0;
for(int j = 0; j < O.size(); ++j){
int cnt = 0;
for(int i = 0; i < selected.size(); ++i){
if(O[j].find(selected[i]) != O[j].end())
++cnt;
}
if(cnt == selected.size())
++ret;
}
return ret;
}
void dfs(int size, char prec, vector<char>& selected){
if(size == selected.size()){
int cnt = getCount(selected);
string tmp = ""; for(int j = 0; j < selected.size(); ++j) tmp += selected[j];
nn.push_back({tmp, cnt});
if(nmax == -1 || nmax < cnt) nmax = cnt;
return;
}
for(char c = prec + 1; c <= 'Z'; ++c){
selected.push_back(c);
dfs(size, c, selected);
selected.pop_back();
}
}
vector<string> solution(vector<string> orders, vector<int> course) {
vector<string> ans;
O.clear();
for(int j = 0; j < orders.size(); ++j){
O.push_back(set(orders[j].begin(), orders[j].end()));
}
for(int j = 0; j < course.size(); ++j){
vector<char> sel;
nmax = -1;
nn.clear();
dfs(course[j], 'A' - 1, sel);
for(int i = 0; i < nn.size() && nmax >= 2; ++i){
if(nn[i].cnt == nmax){
ans.push_back(nn[i].str);
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
문제3.
각 지원자들에 대한 정보가 담겨있는 배열 info와 각 쿼리가 담긴 배열 query가 주어졌을 때, 각 쿼리에 주어진 조건을 만족하는 지원자들이 몇명인지 구하는 문제다.
풀이
주어진 정보들은 5가지이고 이중 4가지 정보는 각각 2 ~ 3개의 값만 가진다. 이를 이용하여 점수를 담는 4차원 배열 vector<int> P[3][2][2][2]을 만들 수 있다. 그리고 각 점수들을 분류해서 배열에 담아준다.
점수들을 모두 담아준 뒤 각각의 배열을 모두 정렬해준다. 쿼리들을 처리하기 전에 전처리로 정렬을 해두면 각 조건에 대해 x점 이상인 사람을 찾는 작업을 이분탐색으로 빠르게 처리할 수 있다.
이후 각 쿼리들을 돌면서 조건에 해당하는 사람 수를 구하는 작업을 수행한다. 여기서 조건이 -로 주어졌다면 해당 조건에 해당하는 배열 P의 모든 인덱스를 탐색하고 그렇지 않다면 주어진 조건에 해당하는 인덱스만 탐색해 주면 된다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> P[3][2][2][2];
int getIdx(string str){
if(str == "cpp") return 0;
if(str == "java") return 1;
if(str == "python") return 2;
if(str == "backend") return 0;
if(str == "frontend") return 1;
if(str == "junior") return 0;
if(str == "senior") return 1;
if(str == "chicken") return 0;
if(str == "pizza") return 1;
return -1;
}
int get(vector<int>& arr, int score){
if(arr.size() == 0) return 0;
int idx = lower_bound(arr.begin(), arr.end(), score) - arr.begin();
return arr.size() - idx;
}
int getCount(string q){
int ret = 0;
vector<string> sp;
string tmp = "";
for(int j = 0; j < q.size(); ++j){
if(q[j] == ' '){
sp.push_back(tmp);
tmp = "";
if(sp.size() < 4)
j += 4;
}else tmp += q[j];
}
int score = stoi(tmp);
vector<int> idx;
for(int j = 0; j < 4; ++j)
idx.push_back(getIdx(sp[j]));
for(int i1 = 0; i1 < 3; ++i1){
if(idx[0] != -1 && idx[0] != i1) continue;
for(int i2 = 0; i2 < 2; ++i2){
if(idx[1] != -1 && idx[1] != i2) continue;
for(int i3 = 0; i3 < 2; ++i3){
if(idx[2] != -1 && idx[2] != i3) continue;
for(int i4 = 0; i4 < 2; ++i4){
if(idx[3] != -1 && idx[3] != i4) continue;
ret += get(P[i1][i2][i3][i4], score);
}
}
}
}
return ret;
}
vector<int> solution(vector<string> info, vector<string> query) {
vector<int> ans;
for(int j = 0; j < info.size(); ++j){
vector<string> sp;
string tmp = "";
for(int i = 0; i < info[j].size(); ++i){
if(info[j][i] == ' '){
sp.push_back(tmp);
tmp = "";
}else
tmp += info[j][i];
}
int score = stoi(tmp);
int i1, i2, i3, i4;
i1 = getIdx(sp[0]);
i2 = getIdx(sp[1]);
i3 = getIdx(sp[2]);
i4 = getIdx(sp[3]);
P[i1][i2][i3][i4].push_back(score);
}
for(int i1 = 0; i1 < 3; ++i1)
for(int i2 = 0; i2 < 2; ++i2)
for(int i3 = 0; i3 < 2; ++i3)
for(int i4 = 0; i4 < 2; ++i4)
sort(P[i1][i2][i3][i4].begin(), P[i1][i2][i3][i4].end());
for(int j = 0; j < query.size(); ++j){
ans.push_back(getCount(query[j]));
}
return ans;
}
문제 4.
무향 그래프가 주어진다. 각 그래프의 간선은 자연수의 비용을 가진다. 이때 주어진 시작 정점 S에서 두 사람의 집이 위치한 두 정점 A, B에 각각 이동하는 데에 드는 최소비용을 구해야 한다. 여기서 두 사람은 출발 정점에서 같이 이동하여 비용을 줄일 수 있다.
풀이
최단거리 문제인데 “같이 이동할 수 있다”는 조건이 추가된 문제다.
정점의 개수는 최대 200개에 불과하므로 동시에 이동하는 정점 u를 잡고 S에서 u까지의 최소 비용과 u에서 A, B정점 각각으로 이동하는 최소 비용의 합을 구한 뒤, 이 값들 중 최솟값을 구하면 된다.
그렇다면 임의의 두 정점에 대한 최소 비용을 구해야 하는데, 이는 모든 정점 쌍들에 대한 최소 비용을 구하는 문제와 같으므로 잘 알려진 알고리즘인 플로이드-워셜 알고리즘을 사용하면 쉽게 해결된다.
#include <string>
#include <vector>
#define INF 2147483647
#define MAXN 200
using namespace std;
int dist[MAXN + 1][MAXN + 1];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int ans = INF;
for(int s = 1; s <= n; ++s)
for(int e = 1; e <= n; ++e){
if(s == e) dist[s][e] = 0;
else dist[s][e] = INF;
}
for(int j = 0; j < fares.size(); ++j){
int v = fares[j][0], u = fares[j][1], c = fares[j][2];
dist[v][u] = dist[u][v] = c;
}
for(int u = 1; u <= n; ++u)
for(int s = 1; s <= n; ++s)
for(int e = 1; e <= n; ++e)
if(dist[s][u] < INF && dist[u][e] < INF)
if(dist[s][u] + dist[u][e] < dist[s][e])
dist[s][e] = dist[s][u] + dist[u][e];
for(int u = 1; u <= n; ++u){
int cost = dist[s][u] + dist[u][a] + dist[u][b];
if(cost < ans) ans = cost;
}
return ans;
}
문제 5.
영상의 길이, 광고의 길이, 시청 로그들이 주어졌을 때, 총 광고 시청 시간이 최댓값이 되도록 하는 광고 시작 위치를 찾는 문제다.
풀이
단순히 생각하면 영상의 길이 만큼의 길이를 가진 배열을 만들고 각 시청 로그들의 시간대에 해당하는 인덱스에 1씩 더해준다. 그렇다면 각 인덱스 i에 대해 i에서 부터 광고의 길이만큼의 구간에서의 배열의 구간 합의 값이 i에서 부터 광고를 두었을 때 총 광고 시청시간임을 알 수 있다.
하지만 각 구간의 최대 길이는 0~99시간 59분 59초 즉, 약 360,000이므로 naive하게 구현할 경우 시간 비용이 매우 크다.
이를 효율적으로 해결하는 방법으로 Segment tree with lazy propagation 자료구조를 이용할 수 있다. 각 구간에 대한 업데이트/구간합이 $O(\log{N})$에 해결되므로 빠르게 문제를 해결할 수 있다.
#include <string>
#include <vector>
using namespace std;
typedef long long int lli;
class SegmentTree{
private:
vector<lli> seg, lazy;
int size;
int left(int idx){
return (idx + 1) * 2 - 1;
}
int right(int idx){
return (idx + 1) * 2;
}
void lazyPropagation(int idx, int ns, int ne){
if(lazy[idx]){
seg[idx] += lazy[idx] * (ne - ns + 1);
if(ns < ne){
lazy[left(idx)] += lazy[idx];
lazy[right(idx)] += lazy[idx];
}
lazy[idx] = 0;
}
}
public:
SegmentTree(int size){
seg.resize(size * 4, 0);
lazy.resize(size * 4, 0);
this->size = size;
}
void update(int idx, int s, int e, int ns, int ne, lli v){
lazyPropagation(idx, ns, ne);
if(e < ns || s > ne)
return;
if(s <= ns && ne <= e){
lazy[idx] += v;
lazyPropagation(idx, ns, ne);
return;
}
int mid = (ns + ne) >> 1;
update(left(idx), s, e, ns, mid, v);
update(right(idx), s, e, mid + 1, ne, v);
seg[idx] = seg[left(idx)] + seg[right(idx)];
}
lli get(int idx, int s, int e, int ns, int ne){
lazyPropagation(idx, ns, ne);
if(e < ns || s > ne)
return 0;
if(s <= ns && ne <= e){
return seg[idx];
}
int mid = (ns + ne) >> 1;
return get(left(idx), s, e, ns, mid) + get(right(idx), s, e, mid + 1, ne);
}
void uquery(int s, int e, int v){
update(0, s, e, 0, size, v);
}
lli query(int s, int e){
return get(0, s, min(e, size), 0, size);
}
};
int parseTime(string tt){
int hh, mm, ss;
hh = (tt[0] - '0') * 10 + tt[1] - '0';
mm = (tt[3] - '0') * 10 + tt[4] - '0';
ss = (tt[6] - '0') * 10 + tt[7] - '0';
return hh * 60 * 60 + mm * 60 + ss;
}
string intToString(int tt){
string ret = "";
if(tt < 10){
ret += '0';
ret += (char)tt + '0';
}else{
ret += (char)(tt / 10) + '0';
ret += (char)(tt % 10) + '0';
}
return ret;
}
string secondsToString(int tt){
int hh, mm, ss;
hh = tt / (60 * 60); tt -= hh * 60 * 60;
mm = tt / 60; tt -= mm * 60;
ss = tt;
return intToString(hh) + ":" + intToString(mm) + ":" + intToString(ss);
}
string solution(string play_time, string adv_time, vector<string> logs) {
string ans = "";
int playTime = parseTime(play_time);
int advTime = parseTime(adv_time);
SegmentTree seg(playTime * 2);
for(int j = 0; j < logs.size(); ++j){
string st = "", et = "";
for(int i = 0; i < 8; ++i)
st += logs[j][i];
for(int i = 0; i < 8; ++i)
et += logs[j][9 + i];
int stt = parseTime(st);
int ett = parseTime(et);
seg.uquery(stt, ett - 1, 1);
}
lli mm = -1;
for(int st = 0; st < playTime; ++st){
lli tt = seg.query(st, st + advTime - 1);
if(mm < tt){
ans = secondsToString(st);
mm = tt;
}
}
return ans;
}
문제 6.
4x4 크기의 배열과 배열에서의 시작 위치가 주어진다. 이 배열에서 0은 카드가 없는 부분을 뜻하고 1 ~ 6의 값은 카드의 종류를 뜻한다. 각 종류에 대해 2가지 카드가 주어진다. 같은 숫자들에 대해 연속해서 Enter키를 누르는 조작을 수행하면 카드를 없앨 수 있다. 이를 위해 커서의 위치를 이동시켜야 하는데 커서를 이동하는 방법은 다음과 같다.
- 상하좌우 중 한 방향으로 한칸 이동한다.
- 상하좌우 중 한 방향으로 다른 카드가 존재하는 위치로 이동한다.
- 단, 해당 방향에 카드가 없는 경우 마지막 칸으로 이동한다.
각 이동은 조작 횟수 1의 비용을 가진다.
이런 상황에서 모든 카드를 없애는 최소 비용을 구하는 문제다.
풀이
우선 하나의 카드에 대해 처음으로 선택한 경우를 생각해 보자. 이 경우 같은 종류에 해당하는 다른 카드로 최단경로로 이동하는 방법 밖에 없음을 알 수 있다.
따라서 다음의 과정을 dfs로 구현하여 탐색하면 된다.
- 남아있는 카드 중 임의의 카드 하나를 선택한다.
- 해당 카드의 종류에 해당하는 나머지 카드 하나를 선택한다.
각 선택을 위해서는 최단 비용을 구해야 하는데 이는 BFS로 구현해주면 된다.
#include <string>
#include <vector>
#include <queue>
#define INF 2147483647
using namespace std;
struct point{
int x, y;
};
struct strt{
point p;
int cost;
};
int width = 4, height = 4;
int DIR[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int shortest(vector<vector<int>>& board, point s, point e){
queue<strt> q;
vector<vector<int>> visit;
visit.resize(height);
for(int y = 0; y < height; ++y) visit[y].resize(width, -1);
visit[s.y][s.x] = 0;
q.push({s, 0});
while(!q.empty()){
strt t = q.front(); q.pop();
point p = t.p;
if(visit[p.y][p.x] != -1 && t.cost > visit[p.y][p.x])
continue;
for(int j = 0; j < 4; ++j){
int nx = p.x + DIR[j][0];
int ny = p.y + DIR[j][1];
if(nx < 0 || ny < 0 || nx >= width || ny >= height)
continue;
if(visit[ny][nx] == -1 || visit[ny][nx] > t.cost + 1){
visit[ny][nx] = t.cost + 1;
q.push({ {nx, ny}, t.cost + 1});
}
while(board[ny][nx] == 0){
if(nx + DIR[j][0] < 0 || ny + DIR[j][1] < 0
|| nx + DIR[j][0] >= width || ny + DIR[j][1] >= height)
break;
nx += DIR[j][0];
ny += DIR[j][1];
}
if(visit[ny][nx] == -1 || visit[ny][nx] > t.cost + 1){
visit[ny][nx] = t.cost + 1;
q.push({ {nx, ny}, t.cost + 1});
}
}
}
return visit[e.y][e.x];
}
int dfs(vector<vector<int>>& board, int sx, int sy){
int mincost = INF;
for(int y = 0; y < height; ++y){
for(int x = 0; x < width; ++x){
if(!board[y][x]) continue;
int dist = shortest(board, {sx, sy}, {x, y});
int nx, ny;
for(int ty = 0; ty < height; ++ty)
for(int tx = 0; tx < width; ++tx){
if(tx == x && ty == y) continue;
if(board[ty][tx] == board[y][x]){
dist += shortest(board, {x, y}, {tx, ty});
nx = tx; ny = ty;
}
}
dist += 2;
int tmp = board[ny][nx];
board[ny][nx] = board[y][x] = 0;
mincost = min(mincost, dist + dfs(board, nx, ny));
board[ny][nx] = board[y][x] = tmp;
}
}
if(mincost == INF)
return 0;
return mincost;
}
int solution(vector<vector<int>> board, int r, int c) {
int ans = 0;
ans = dfs(board, c, r);
return ans;
}
문제 7.
회사의 조직도가 주어진다. 조직도는 유향 트리 구조이며, 각 직원은 정점으로 나타내어 지며 팀장 또는 팀원이거나 둘 다이다. 즉, 직계 자식이 존재하는 각 정점에 대해 해당 정점과 자식 정점들이 팀 하나를 이룬다. 따라서 각 직원은 최대 2개 팀에 소속된다.
각 팀에서 최소 1명의 직원을 뽑을 때, 뽑힌 직원들의 각 하루 평균 매출액의 합의 최솟값을 구하는 문제다.
풀이
우선 트리에서 가장 아래에 위치한 팀을 생각해 보자. (즉, leaf node가 포함된 팀) 해당 팀에서 팀장을 선택한 경우와 팀장을 선택하지 않은 경우 각각에 대한 최솟값은 쉽게 구할 수 있다. 그렇다면 해당 팀장을 팀원으로 포함하는 팀에서도 마찬가지로 팀장을 선택한 경우와 팀장을 선택하지 않은 경우를 구할 수 있다. 이는 팀원 각 노드들에 대해 서로 중복되는 직원을 자식으로 가지지 않으므로 선택한 경우/선택하지 않은 경우 중에 최솟값을 합해가는 방식으로 구할 수 있다.
이러한 과정을 leaf node에서 root node까지 구해 나가면 해결된다. 구해 나가는 과정은 후위순회로 구현할 수 있다.
#include <string>
#include <vector>
#include <algorithm>
#define INF 2147483647
#define MAXN 300000
using namespace std;
vector<int> G[MAXN + 1], cost;
int dp[MAXN + 1][2];
void dfs(int v){
int nmin = INF;
for(int j = 0; j < G[v].size(); ++j)
dfs(G[v][j]);
if(G[v].size() == 0){
dp[v][0] = 0;
dp[v][1] = cost[v];
return;
}
int cc = 0, cnt = 0;
for(int j = 0; j < G[v].size(); ++j){
int u = G[v][j];
cc += min(dp[u][0], dp[u][1]);
if(dp[u][0] >= dp[u][1]) ++cnt;
}
dp[v][1] = cc + cost[v];
if(cnt > 0){
dp[v][0] = cc;
}else{
for(int j = 0; j < G[v].size(); ++j){
int u = G[v][j];
if(dp[u][0] <= dp[u][1])
nmin = min(nmin, cc - dp[u][0] + dp[u][1]);
}
dp[v][0] = nmin;
}
}
int solution(vector<int> sales, vector<vector<int>> links) {
int ans = 0;
cost.resize(sales.size() + 1);
for(int j = 0; j < sales.size(); ++j)
cost[j + 1] = sales[j];
for(int j = 0; j < links.size(); ++j)
G[links[j][0]].push_back(links[j][1]);
dfs(1);
ans = min(dp[1][0], dp[1][1]);
return ans;
}