2021 카카오 인턴십 코딩테스트
2021 카카오 인턴십? 이란게 있었어서 풀어봤다. 블라인드 채용이랑 다른건가보다.
2021 블라인드 채용도 저번에 풀어봤는데,
저번에 푼건 7문제인데, 이번에 푼건 5문제이다. 제한시간은 4시간이였다고 한다.
퇴근하고 2번까지 풀고 중간에 초밥을 먹고 다시 풀었으니,
다 푸는데 2시간 ~ 2시간 반 정도 걸린 것 같다.
5번에서 거의 1시간 좀 넘게 쓴것같다.
1. 숫자 문자열과 영단어
프로그래머스 레벨: Level 1
체감 티어: 브론즈 1
문자열, 구현
오우,, 문제 보자마자 바로 kotlin 켜서 풀었다. C++ 로 들어갔다가 정신이 혼미해질뻔 했다.
문자열 내장함수를 잘 지원해주는 언어들에서 replace 를 이용해 쓱 풀면 된다.
fun solution(ss: String): Int {
var s = ss
s = s.replace("zero", "0")
s = s.replace("one", "1")
s = s.replace("two", "2")
s = s.replace("three", "3")
s = s.replace("four", "4")
s = s.replace("five", "5")
s = s.replace("six", "6")
s = s.replace("seven", "7")
s = s.replace("eight", "8")
s = s.replace("nine", "9")
return s.toInt()
}
2. 거리두기 확인하기
프로그래머스 레벨: Level 2
체감 티어: 실버 4
브루트포스
단순한 구현 문제이다. 브루트포스로 구현을 해주면 된다.
맨하탄 거리가 2이하인건 하나의 지점에서 12개가 있는데, 12개를 모두다 해줄 필요는 없다.
6개만 해주면 나머지 6개는 다른 정점에서 체크되기 때문이다.
한 10개까지 구현을 해준다음에야 깨달았다.
실수없이 구현을 하면 빠르게 풀 수 있다.
vector<int> solution(vector<vector<string>> places) {
vector<int> answer;
for(auto& p: places){
for(int y = 0; y < 5; y++){
for(int x = 0; x < 5; x++){
if(p[y][x] != 'P') continue;
if(y > 0 && p[y-1][x] == 'P') goto skip;
if(x > 0 && p[y][x-1] == 'P') goto skip;
if(y > 0 && x > 0){
if(p[y-1][x-1] == 'P' && (p[y-1][x] == 'O' || p[y][x-1] == 'O')) goto skip;
}
if(y > 0 && x < 4){
if(p[y-1][x+1] == 'P' && (p[y-1][x] == 'O' || p[y][x+1] == 'O')) goto skip;
}
if(y>1 && p[y-2][x] == 'P' && p[y-1][x] == 'O') goto skip;
if(x>1 && p[y][x-2] == 'P' && p[y][x-1] == 'O') goto skip;
}
}
answer.push_back(1);
continue;
skip:;
answer.push_back(0);
}
return answer;
}
3. 표 편집
프로그래머스 레벨: Level 3
체감 티어: 골드 4
스택, 이분탐색, 세그먼트 트리
이 문제는 보고 x의 총합이 100만 이하라서 그럼 그렇지하고 그냥 리스트로 1칸씩 이동하면서 구현하면 되는 줄 알았는데, 중간에 몇십만개가 비어있고 계속 U, D 를 1씩 줘서 그 사이를 건너뛰게 된다면 시간 초과가 남을 알 수 있다.
그래서 링크드 리스트랑 삭제 정보를 저장해두는 스택을 잘 구현하면 문제가 풀린다는걸 깨달았는데, 더 쉬운 방법으로 풀기로 했다.
세그먼트 트리를 써서 U, D 연산을 $O(log^{2N})$에 처리해줄 수 있기 때문이다.
이진 탐색을 쓰면 되는데, 간만에 펜윅 트리도 템플릿 안쓰고 직접 구현해봤는데 한번에 잘돼서 뿌듯했다.
struct fenwick {
vector<int> tree;
fenwick(int n) { tree.resize(n + 1); }
void update(int i, int v) {
i++;
while (i <= tree.size()) {
tree[i] += v;
i += i & -i;
}
}
int sum(int i) {
int ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
int query(int l, int r) {
return sum(r + 1) - sum(l);
}
};
string solution(int n, int k, vector<string> cmd) {
string answer;
fenwick fenw(n);
for (int i = 0; i < n; i++) fenw.update(i, 1);
auto idx = [&](int diff) {
int ret = 0;
if (diff < 0) {
diff = -diff;
int l = 0, r = k - 1;
while (l <= r) {
int m = (l + r) / 2;
if (fenw.query(m, k - 1) >= diff) {
ret = m;
l = m + 1;
} else r = m - 1;
}
} else {
int l = k + 1, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
if (fenw.query(k + 1, m) >= diff) {
ret = m;
r = m - 1;
} else l = m + 1;
}
}
return ret;
};
vector<int> deleted;
for (auto &c: cmd) {
if (c[0] == 'U') {
int m = stoi(c.substr(2));
k = idx(-m);
} else if (c[0] == 'D') {
int m = stoi(c.substr(2));
k = idx(m);
} else if (c[0] == 'C') {
deleted.push_back(k);
fenw.update(k, -1);
if (fenw.query(k + 1, n - 1) == 0) {
k = idx(-1);
} else {
k = idx(1);
}
} else {
fenw.update(deleted.back(), 1);
deleted.pop_back();
}
}
for (int i = 0; i < n; i++) {
answer += (fenw.query(i, i) ? 'O' : 'X');
}
return answer;
}
4. 미로 탈출
프로그래머스 레벨: Level 4
체감 티어: 골드 2
BFS, 비트마스킹
이것도 BFS를 많이 푼 사람이라면 그리 어렵지않게 아이디어를 떠올릴 수 있다.
근데 비트연산이 추가되어서 약간 난이도를 높게 줄 수 있을 것 같다.
문제를 처음보고 바로 노드의 개수와 트랩의 개수를 확인했는데, 트랩의 개수가 10개 이하인거에서 바로 비트마스킹의 악취가 풀풀 나기 시작했다.
하나의 정점을 <정점 번호, 뒤집혀있는 함정들 비트> 로 생각할 수 있다.
$1000 \cdot 2^{10}$ 이기 때문에 충분히 최단거리를 구할 수 있는 수준이다.
그리고 정점도 그렇게 많지 않아서 굳이 다익스트라로 안풀고 그냥 BFS만 써줬다.
간선을 저장할 때 $u \to v$ 여도, $v \to u$ 도 모두 저장해두는게 편하다. 왜냐면 간선의 방향이 반대가 될 수 있기 때문이다.
현재 반대로 처리해줘야 하는지는 비트마스킹을 통해 반대편 정점과 현재 있는 정점이 트랩인지, 반전되어있는 지를 통해 적절히 판단해주면 된다.
그리고 간선중 쓸 수 있는것만 써보는 것이다.
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
start--, end--;
vector<vector<vector<int>>> edges(n);
for (auto &v: roads) {
int f = v[0], t = v[1], c = v[2];
f--, t--;
edges[f].push_back({t, c, 0});
edges[t].push_back({f, c, 1});
}
vector<int> trap(n, -1);
for (int i = 0; i < traps.size(); i++) trap[traps[i] - 1] = i;
vector<vector<int>> dist(n, vector<int>(1 << 11, 1e9));
dist[start][0] = 0;
queue<pair<int, int>> q;
q.push({start, 0});
int ans = 1e9;
while (q.size()) {
auto &v = q.front();
int cur = v.first, bit = v.second;
q.pop();
if (cur == end) {
ans = min(ans, dist[cur][bit]);
continue;
}
for (auto &v: edges[cur]) {
int to = v[0], cost = v[1];
int t1 = trap[cur], t2 = trap[to], cnt = 0;
if (t1 != -1 && (bit & (1 << t1)))cnt++;
if (t2 != -1 && (bit & (1 << t2)))cnt++;
if (cnt % 2 != v[2]) continue;
int next_bit = t2 == -1 ? bit : (bit ^ (1 << t2));
if (dist[to][next_bit] > cost + dist[cur][bit]) {
dist[to][next_bit] = cost + dist[cur][bit];
q.push({to, next_bit});
}
}
}
return ans;
}
5. 시험장 나누기
프로그래머스 레벨: Level 5
체감 티어: 플레티넘 3
트리, 위상 정렬, 그리디 알고리즘, 매개변수(이분) 탐색
어우 이거 너무 어려웠다. 프로그래머스에서 레벨 5짜리는 처음풀어보는듯하다.
일단 저번에 2021 카카오 블라인드 채용 마지막 문제로 트리에서의 다이나믹 프로그래밍이 나오길래 이것도 그건줄 알고, 다이나믹 프로그래밍으로 접근을 계속 시도했다.
근데 $N$과 $K$가 모두 $10{,}000$ 인걸 보고 2차원 배열을 잡는것부터가 불가능하기 때문에 DP는 아닌걸 알았다.
그 와중에 생각난게 이분 탐색이였는데, 일단 어떤 그룹을 최대 $M$ 이하로 묶었을 때 최대 $k$개의 그룹으로 묶을 수 있는지를 판단하는 데 이분 탐색이 쓰이면 될 것 같았다. 이런 유형을 풀어본거같기도 하고
근데 우리가 K개의 그룹을 딱 만들어야 되는 조건인데, 이는 맞추기가 굉장히 까다롭다. 한 그룹에 최대 M 이하로 묶어서 그룹을 지었는데 그게 K개보다 작을수도 있지 않은가?
하지만 우린 그 조건을 무시하고 $K$개 이하의 그룹만 만들어 줄 수 있는지 보면 된다.
$\quad\because K$개 이하의 그룹들을 만든다면, 어떤 그룹을 한번 쪼개서 항상 현재 그룹의 개수 + 1 을 해줄 수가 있는데(트리이기 때문), 쪼개진 그룹들은 원래도 사람수 합이 $M$ 이하였는데 쪼개지면 무조건 작아질 것이기 때문에 상관이 없다.
즉, $K$개 이하의 그룹들이 만듦이 보장되면 $K$개의 그룹도 만들 수 있음이 보장된다.
그 다음으론, 한 그룹의 최대 사람수가 $M$이면서 $K$개의 그룹 이하의 그룹을 만들 수 있는것을 어떻게 판단해줄것이냐?
보통 트리 문제는 루트부터 내려가는데, 이 문제에선 leaf 노드들부터 올라가며 위상정렬을 해주는 아이디어를 떠올릴 수 있었다.
아마 루트부터 내려오는 방법도 있을것이라 생각한다.
일단, 위상정렬을 하며 그룹의 개수를 계속 올려준다.
언제마다? 다음 노드를 포함하면 $M$ 보다 커지는 순간까지
여기서 그리디 알고리즘이 쓰인다.
어떤 부모 노드 $A$가 있고 자식 $B,\,C$가 있다고 하자.
부모 노드 $A$가 $B$가 루트로 있는 그룹의 합, $C$가 루트로 있는 그룹의 합과 자기 자신을 다 더하고도 사람 수가 $M$ 이하라고 해보자.
그럼 그냥 다 병합해버리는 것이다.
그렇게 안된다면, 더 사람이 적은 그룹의 자식껏과 병합을 시도한다.
그것도 안된다면 그냥 자기혼자 새로운 그룹을 만든다.
이것도 그리디 알고리즘이다.
이렇게 쭉쭉 루트로 위상정렬을 하면서 올라가면 총 필요한 그룹 수가 나온다.
여담으로 시험장 나누기 문제는, 백준에서도 비슷한 문제가 있다.
코드를 조금 고쳐 제출했더니 바로 맞았다.
코드가 썩 깔끔하진 않다. 시험장 나누기 문제는 이진트리이기 때문에 코드가 대충짜여있다.
이 문제는 템플릿없이 풀다가 정신이 혼미해질것 같았기 때문에 내 c++ 템플릿과 함께 풀었다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);
#define endl "\n"
#define pb push_back
#define all(X) (X).begin(), (X).end()
#define sz(X) (int)(X).size()
#define fi first
#define se second
#define fv(X) for(auto&_:(X))cin>>_
#define fv1(X) for(int _=1;_<sz(X);_++)cin>>(X)[_]
#define fv2(X) for(auto&__:(X))fv(__)
#define lbi(X, n) (lower_bound(all(X), n) - begin(X))
#define ubi(X, n) (upper_bound(all(X), n) - begin(X))
#define maxi(X) max_element(all(X)) - begin(X)
#define maxe(X) *max_element(all(X))
#define mini(X) min_element(all(X)) - begin(X)
#define mine(X) *min_element(all(X))
#define acc(X) accumulate(all(X), 0LL)
#define cntt(X, x) count(all(X),x)
#define mp(a, b) make_pair((a),(b))
#define has(X, x) (find(all((X)),x)!=(X).end())
#define hass(X, x) ((X).count(x) > 0)
#define hasstr(X, x) (!!strstr(&(X)[0],&(x)[0]))
#define uniq(X) sort(all(X)); (X).resize(unique(all((X))) - (X).begin())
int solution(int k, vector<int> num, vector<vector<int>> c) {
int n = sz(num), total = acc(num), ans = -1;
vi p(n, -1), leaf, entry_original(n);
for (int i = 0; i < n; i++) {
if (c[i][0] != -1) {
p[c[i][0]] = i;
entry_original[i]++;
}
if (c[i][1] != -1) {
p[c[i][1]] = i;
entry_original[i]++;
}
if (c[i][0] == -1 && c[i][1] == -1) leaf.pb(i);
}
int l = 0, r = total;
while (l <= r) {
int m = (l + r) / 2;
vi entry = entry_original, sum(n);
queue<int> q;
for (auto i: leaf) q.push(i);
int group = 0, flag = true;
while (sz(q)) {
int cur = q.front();
q.pop();
sum[cur] += num[cur];
if (num[cur] > m) {
flag = false;
break;
}
int lc = c[cur][0], rc = c[cur][1];
if (lc != -1 && rc != -1) {
if (sum[lc] + sum[rc] + sum[cur] <= m) {
group--;
sum[cur] += sum[lc] + sum[rc];
} else if (sum[lc] < sum[rc]) {
if (sum[lc] + sum[cur] <= m) {
sum[cur] += sum[lc];
} else {
group++;
}
} else {
if (sum[rc] + sum[cur] <= m) {
sum[cur] += sum[rc];
} else {
group++;
}
}
} else if (lc != -1) {
if (sum[lc] + sum[cur] <= m) {
sum[cur] += sum[lc];
} else {
group++;
}
} else if (rc != -1) {
if (sum[rc] + sum[cur] <= m) {
sum[cur] += sum[rc];
} else {
group++;
}
} else {
group++;
}
if (p[cur] != -1) {
entry[p[cur]]--;
if (entry[p[cur]] == 0) {
q.push(p[cur]);
}
}
}
if (flag && group <= k) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
Comments