오늘 진행된 2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트에 참여하고 출제된 문제 7개에 대한 풀이를 남긴다.
문제1.
각 유저의 id와 각 유저가 신고한 정보, 그리고 정지 기준이 되는 신고 횟수 $k$가 주어진다. 한 유저가 0명 이상의 다른 유저를 신고할 수 있고, 동일한 유저를 여러번 신고할 시 1회 신고한 것으로 처리되며, $k$번 이상 신고를 당한 유저는 정지되고 해당 유저를 신고한 유저들에게 이메일이 전송된다. 정지당한 유저도 신고를 할 수 있을 때, 각 유저별로 이메일을 받은 횟수를 반환하는 문제다.
풀이
각 유저에 대해서 신고한 유저 아이디 목록을 unique하게 만든 뒤, 각 유저 별로 신고를 당한 횟수를 계산한다. 이후 각 유저에 대해 탐색하면서 신고한 유저 중에 $k$회 이상 신고를 당한 사람의 수를 계산하여 정답에 반영한다.
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
vector<int> ans;
map<string, int> reported;
map<string, set<string>> reported_users_by_user;
for(int j = 0; j < id_list.size(); ++j){
reported[id_list[j]] = 0;
}
for(int j = 0; j < report.size(); ++j){
string user = "";
string reported_user = "";
int i = 0;
for(; i < report[j].size(); ++i){
if(report[j][i] == ' ') break;
user += report[j][i];
}
for(++i; i < report[j].size(); ++i){
reported_user += report[j][i];
}
if(reported_users_by_user[user].find(reported_user) == reported_users_by_user[user].end()){
reported[reported_user]++;
reported_users_by_user[user].insert(reported_user);
}
}
for(int j = 0; j < id_list.size(); ++j){
int recv = 0;
for(auto itr = reported_users_by_user[id_list[j]].begin(); itr != reported_users_by_user[id_list[j]].end(); ++itr){
if(reported[*itr] >= k){
++recv;
}
}
ans.push_back(recv);
}
return ans;
}
문제2.
양의 정수 $n$과 $k$가 주어진다. ($1\leq n \leq 1,000,000$, $3\leq k\leq 10$) $n$을 $k$진수로 변환했을 때, 다음 조건에 해당하는 소수(prime number)가 몇 개인지 반환한다. (중복되는 소수를 발견해도 따로 센다)
0P0처럼 소수 양 쪽에 0이 있는 경우P0처럼 소수 오른쪽에 0이 있는 경우0P처럼 소수 왼쪽에 0이 있는 경우P처럼 소수 양 쪽에 아무것도 없는 경우P는 각 자리에 0이 포함하지 않음
풀이
결국은 문자 0을 기준으로 split하여 나온 각 숫자에 대해 소수판별을 하는 문제다.
주어진 $n$의 최댓값을 $k$진수로 변환했을 때, 가장 길게 나올 수 있는 경우를 고려하여 자료형을 맞춰주면 된다.
#include <string>
#include <vector>
#include <stack>
using namespace std;
typedef long long int lli;
bool check_prime(lli num){
if(num <= 1) return false;
for(lli j = 2; j * j <= num; ++j){
if(num % j == 0) return false;
}
return true;
}
int solution(int n, int k) {
int ans = 0;
string converted = "";
stack<int> stk;
for(int t = n; t; t /= k){
stk.push(t % k);
}
while(!stk.empty()){
converted += (char)(stk.top() + '0');
stk.pop();
}
vector<string> nums;
string str = "";
for(int j = 0; j < converted.size(); ++j){
if(converted[j] == '0'){
if(str.size() > 0){
nums.push_back(str);
str = "";
}
}else{
str += converted[j];
}
}
if(str.size() > 0) nums.push_back(str);
for(int j = 0; j < nums.size(); ++j){
lli num = 0;
for(int i = 0; i < nums[j].size(); ++i){
num = num * 10 + nums[j][i] - '0';
}
if(check_prime(num)){
ans++;
}
}
return ans;
}
문제3.
기본 시간, 기본 요금, 단위 시간, 단위 요금 네가지 정수가 담긴 길이 4의 정수배열 fees와 각 자동차의 출차기록이 담긴 배열 records가 주어진다. (records길이는 1,000이하) records의 각 원소에는 HH:MM형식의 출차 시각, 길이 4의 차량번호, IN 또는 OUT인 내역으로 구성된다. (예 - 05:34 0000 IN)
00:00 부터 23:59까지의 입/출차 내역을 바탕으로 차량별 누적 주차 시간을 계산하여 요금을 일괄로 계산한다. 마지막 출차 기록이 없다면 23:59에 출차되는 것으로 계산한다. 이때, 누적 주차 시간이 기본시간 이하면 기본요금을 청구하고, 기본시간 초과라면 기본요금에 기본요금을 초과한 시간에 대해 단위시간 마다 단위요금을 청구한다. 여기서 초과시간이 단위시간으로 나누어 떨어지지 않으면 올림처리하여 계산할 때, 각 차량 별로 요금을 반환하는 문제다.
풀이
우선 주어진 records를 이용하여 각 자동차 별 출차 시간을 분 단위의 정수로 분리한다. 즉, 각 자동차 별로 정수 배열을 하나씩 가진다.
이후 각 자동차 별로 앞서 구한 정수 배열을 이용하여 누적 시간을 계산한다. 이때, 정수 배열의 길이가 홀수이면 마지막에 출차 기록이 없다는 것이므로 최대 시간인 $23\times 60 + 59$를 배열에 추가해준다.
이후 기본시간과 누적 이용 시간을 비교하여 적절히 처리해준다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> fees, vector<string> records) {
vector<int> ans;
vector<vector<int>> records_by_car;
records_by_car.resize(10000);
for(int j = 0; j < records.size(); ++j){
int hh = (records[j][0] - '0') * 10 + records[j][1] - '0';
int mm = (records[j][3] - '0') * 10 + records[j][4] - '0';
int t = hh * 60 + mm;
int car = 0;
for(int i = 6; i <= 9; ++i) car = car * 10 + records[j][i] - '0';
records_by_car[car].push_back(t);
}
const int MT = 23 * 60 + 59;
for(int j = 0; j < records_by_car.size(); ++j){
if(records_by_car[j].size() == 0) continue;
int tt = 0;
if(records_by_car[j].size() % 2) records_by_car[j].push_back(MT);
for(int i = 0; i < records_by_car[j].size(); i += 2){
int d = records_by_car[j][i + 1] - records_by_car[j][i];
tt += d;
}
if(tt <= fees[0]){
ans.push_back(fees[1]);
}else{
int m = (tt - fees[0]) / fees[2] + ((tt - fees[0]) % fees[2] == 0 ? 0 : 1);
ans.push_back(fees[1] + m * fees[3]);
}
}
return ans;
}
문제 4.
R과 P가 0~10 사이의 정수에 대한 점수가 기록되어 있는 과녁판을 이용하여 양궁 대회를 진행중이다. 각자 화살 $n$발을 쏴서 맞추는데 점수를 얻는 기준은 다음과 같다. ($1\leq n \leq 10$)
- P가 $n$발을 다 쏜 뒤에 R이 쏜다.
- 각 과녁 점수 $k$에 대해, P가 $p$발을 맞췄고, R이 $r$발을 맞췄을 때 다음과 같다.
- $p = r = 0$: 아무도 $k$점을 가져가지 못한다
- $p \leq r$: R이 $k$점을 가져간다
- $p > r$: P가 $k$점을 가져간다
최종 점수가 높은 사람이 승리한다. P가 쏜 점수에 대한 정보가 주어졌을 때, R이 가장 큰 점수 차로 이길 수 있는 경우를 반환하는 문제다. 이때, R이 이길 수 없는 경우는 -1만 담긴 배열을 반환하고, 가장 큰 점수 차로 이길수 있는 경우가 여러개라면 가장 낮은 점수를 더 많이 맞힌 경우를 반환해야 한다.
풀이
$n$이 최대 10인 점을 이용하여 모든 경우에 대해 탐색해주면 된다.
#include <string>
#include <vector>
using namespace std;
int diff = -1;
void dfs(vector<int>& current, vector<int>& info, vector<int>& ans, int j, int rem){
if(j == 10){
current[j] = rem;
int r = 0, p = 0;
for(int i = 0; i <= 10; ++i){
if(!current[i] && !info[i]) continue;
if(current[i] > info[i]){
r += 10 - i;
}else{
p += 10 - i;
}
}
if(r > p && (diff == -1 || diff <= r - p)){
bool f = true;
if(diff != -1 && diff == r - p){
for(int i = 10; i >= 0; --i){
if(ans[i] == current[i]) continue;
if(ans[i] > current[i]){
f = false;
}
break;
}
}
if(f){
diff = r - p;
for(int i = 0; i <= 10; ++i) ans[i] = current[i];
}
}
return;
}
for(int i = rem; i >= 0; --i){
current[j] = i;
dfs(current, info, ans, j + 1, rem - i);
}
}
vector<int> solution(int n, vector<int> info) {
vector<int> current, ans;
current.resize(11, 0);
ans.resize(11, 0);
dfs(current, info, ans, 0, n);
if(diff == -1){
ans.resize(1);
ans[0] = -1;
}
return ans;
}
문제 5.
최소 2개, 최대 17개의 정점으로 이루어진 2진 트리가 주어진다. 각 트리에는 양 또는 늑대가 한마리 살고 있다. 루트 (0번 노드, 항상 양이 살고 있음)에서 부터 출발하여 인접한 정점으로 이동할 때, 방문한 정점에 살고 있는 양/늑대를 휙득한다. 휙득한 양의 개수가 휙득한 늑대의 개수보다 같거나 작다면 늑대가 양들을 모두 잡아먹는다. 이 때, 휙득할 수 있는 양의 최대 마리 수를 구하는 문제다.
풀이
현재 방문한 정점과 인접한 정점에 존재하는 양은 모두 휙득한다. 이후 늑대가 존재하는 인접한 정점들에 대해 DFS하여 모든 경우에 대해 탐색한다. 최대 노드의 개수가 적다는 점에서 가능하다.
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
int dfs(vector<vector<int>>& childs, vector<int>& info, deque<int> snodes, deque<int> wnodes, int s, int w){
if((s || w) && s <= w) return -1;
while(!snodes.empty()){
int sn = snodes.front(); snodes.pop_front();
++s;
for(int j = 0; j < childs[sn].size(); ++j){
int u = childs[sn][j];
if(info[u] == 0){
snodes.push_back(u);
}else{
wnodes.push_back(u);
}
}
}
int ret = s;
for(int j = 0; j < wnodes.size(); ++j){
int wn = wnodes[j];
deque<int> nsnodes, nwnodes;
for(int i = 0; i < snodes.size(); ++i) nsnodes.push_back(snodes[i]);
for(int i = 0; i < wnodes.size(); ++i) if(wnodes[i] != wn) nwnodes.push_back(wnodes[i]);
for(int i = 0; i < childs[wn].size(); ++i){
int u = childs[wn][i];
if(info[u] == 0){
nsnodes.push_back(u);
}else{
nwnodes.push_back(u);
}
}
ret = max(ret, dfs(childs, info, nsnodes, nwnodes, s, w + 1));
}
return ret;
}
int solution(vector<int> info, vector<vector<int>> edges) {
int ans = 0;
vector<vector<int>> childs;
childs.resize(info.size());
for(int j = 0; j < edges.size(); ++j){
childs[edges[j][0]].push_back(edges[j][1]);
}
vector<int> ps(info.size(), 0), pw(info.size(), 0);
deque<int> snodes, wnodes;
snodes.push_back(0);
ans = dfs(childs, info, snodes, wnodes, 0, 0);
return ans;
}
문제 6.
$N\times M$ 크기의 격자 모양 게임 맵이 주어진다. 각 칸에는 건물 하나가 존재하며, 정해진 내구도를 가지고 있다. 이 때, 직사각형 범위에 대한 공격 또는 회복 쿼리가 주어진다. 공격 쿼리에 대해서는 주어진 범위에 속하는 건물의 내구도를 주어진 값 만큼 감소시키고, 회복 쿼리에 대해서는 주어진 범위에 속하는 건물 내구도를 주어진 값 만큼 증가시킨다.
쿼리를 모두 수행한 뒤, 내구도가 1 이상인 건물의 개수를 반환하는 문제이다. 단, 쿼리의 개수는 최대 250,000개이고, $1\leq N, M\leq 1,000$이다.
풀이
라인 스위핑으로 해결할 수 있다. $y$좌표를 기준으로 쓸어갈 때, 탐색중인 $y$좌표에 대한 각 $x$좌표의 값을 1차원 배열인 dp에 업데이트 해준다. dp를 업데이트 할 때에는 탐색중인 $y$좌표에서 시작하는 쿼리와 탐색중인 $y$좌표에서 끝나는 쿼리를 반영해주면 된다. 쿼리를 시작 $y$좌표, 종료 $y$좌표를 기준으로 미리 정렬을 해주면 모든 쿼리를 $O(Q\log{Q} + N + Q)$만에 탐색할 수 있다. 이제 각 쿼리에 대해 시작 $x$좌표, 종료 $x$좌표를 dp에 반영해 주어야 한다. 이는 시작 $x$좌표를 dp2에 반영해 주고, 종료 $x$좌표를 dp3에 반영해 주어서 각 $y$좌표에 대해 $O(M)$만에 dp를 업데이트할 수 있다.
결과적으로 $O(Q\log{Q} + NM + Q) = O(Q\log{Q} + NM)$만에 해결된다.
2d segment tree with lazy propagation 자료구조를 사용하면 쉽게 해결 가능하다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct strt{
int idx, v;
bool operator<(const strt& st)const{
return v < st.v;
}
bool operator>(const strt& st)const{
return v > st.v;
}
};
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int ans = 0;
int height = board.size(), width = board[0].size();
segment_tree seg(width + 1);
vector<strt> pqs, pqe;
vector<pair<int, pair<int, int>>> skills;
for(int j = 0; j < skill.size(); ++j){
int type = skill[j][0];
int r1 = skill[j][1];
int c1 = skill[j][2];
int r2 = skill[j][3];
int c2 = skill[j][4];
int degree = skill[j][5];
if(type == 1) degree = -degree;
skills.push_back({degree, {c1, c2}});
pqs.push_back({j, r1});
pqe.push_back({j, r2});
}
sort(pqs.begin(), pqs.end());
sort(pqe.begin(), pqe.end());
vector<int> dp(width, 0);
for(int y = 0, pqs_idx = 0, pqe_idx = 0; y < height; ++y){
vector<int> dp2(width, 0), dp3(width, 0);
while(pqs_idx < pqs.size() && pqs[pqs_idx].v == y){
int skill_idx = pqs[pqs_idx++].idx;
int sx = skills[skill_idx].second.first;
int ex = skills[skill_idx].second.second;
dp2[sx] += skills[skill_idx].first;
dp3[ex] += skills[skill_idx].first;
}
int ss = 0;
for(int x = 0; x < width; ++x){
ss += dp2[x];
dp[x] += ss;
board[y][x] += dp[x];
if(board[y][x] > 0) ++ans;
ss -= dp3[x];
dp2[x] = 0; dp3[x] = 0;
}
while(pqe_idx < pqe.size() && pqe[pqe_idx].v == y){
int skill_idx = pqe[pqe_idx++].idx;
int sx = skills[skill_idx].second.first;
int ex = skills[skill_idx].second.second;
dp2[sx] += -skills[skill_idx].first;
dp3[ex] += -skills[skill_idx].first;
}
ss = 0;
for(int x = 0; x < width; ++x){
ss += dp2[x];
dp[x] += ss;
ss -= dp3[x];
}
}
return ans;
}
문제 7.
A와 B가 게임을 한다. $N\times M$크기의 보드판 위에서 게임을 하는데, 각 칸 위에는 발판이 있거나 없다. 각 플레이어는 발판이 있는 칸 위에서 시작한다. 플레이어는 A부터 시작하여 서로 번갈아가며 이동하는데, 발판이 존재하는 인접한 칸 (상, 하, 좌, 우)으로 이동할 수 있다. 플레이어가 이동하면 원래 있던 칸의 발판은 사라진다. 다음 두 가지 상황에서 패자와 승자가 결정되고 게임은 종료된다.
- 움직여야 하는 플레이어의 인접 칸에 모두 발판이 없거나 보드판 밖인 경우 패배한다
- 두 플레이어가 같은 칸에 위치할 때, 상대 플레이어가 다른 칸으로 이동하여 발판이 사라진 경우 패배한다
각 플레이어는 최적의 플레이를 하는데, 이길 수 있는 플레이어는 최대한 빨리 이기려고 하고, 질 수밖에 없는 플레이어는 최대한 오래 게임이 지속되도록 한다.
$1\leq N, M\leq 5$일 때, 두 플레이어가 움직인 횟수의 합을 반환하는 문제다.
풀이
게임 이론 문제다. 가능한 모든 경우를 탐색하면서 최적의 경우를 반환하도록 재귀함수를 작성하면 된다. 각자의 턴에서 가능한 4가지 이동을 해보고, 상대방이 이기는 경우와 지는 경우를 처리해준다. 현재 상태에서 질 수 밖에 없다면 플레이를 가장 오래하는 경우를 반환하고, 이길 수 있는 경우가 존재하면 해당 경우 중에서 가장 짧게 플레이하는 경우를 반환한다.
아래 구현에서는 A와 B가 플레이한 경우 각각에 대해 함수를 짜주었지만, 각 플레이어의 위치를 배열로 전달하고 짝수/홀수로 플레이어를 관리하면 하나의 함수로 구현할 수 있다.
#include <string>
#include <vector>
using namespace std;
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
pair<bool, int> bturn(vector<vector<int>>& board, int ax, int ay, int bx, int by);
pair<bool, int> aturn(vector<vector<int>>& board, int ax, int ay, int bx, int by);
pair<bool, int> bturn(vector<vector<int>>& board, int ax, int ay, int bx, int by){
pair<bool, int> ret = {false, -1};
if(!board[by][bx]) return {false, 0};
board[by][bx] = 0;
for(int j = 0; j < 4; ++j){
int nbx = bx + dir[j][0];
int nby = by + dir[j][1];
if(nbx < 0 || nby < 0 || nbx >= board[0].size() || nby >= board.size() || !board[nby][nbx]) continue;
pair<bool, int> aret = aturn(board, ax, ay, nbx, nby);
if(!aret.first){
if(ret.second == -1 || !ret.first || (ret.first && ret.second > aret.second + 1))
ret = {true, aret.second + 1};
}else if(ret.second == -1 || (!ret.first && ret.second < aret.second + 1)){
ret = {false, aret.second + 1};
}
}
board[by][bx] = 1;
if(ret.second == -1) return {false, 0};
return ret;
}
pair<bool, int> aturn(vector<vector<int>>& board, int ax, int ay, int bx, int by){
pair<bool, int> ret = {false, -1};
if(!board[ay][ax]) return {false, 0};
board[ay][ax] = 0;
for(int j = 0; j < 4; ++j){
int nax = ax + dir[j][0];
int nay = ay + dir[j][1];
if(nax < 0 || nay < 0 || nax >= board[0].size() || nay >= board.size() || !board[nay][nax]) continue;
pair<bool, int> bret = bturn(board, nax, nay, bx, by);
if(!bret.first){
if(ret.second == -1 || !ret.first || (ret.first && ret.second > bret.second + 1))
ret = {true, bret.second + 1};
}else if(ret.second == -1 || (!ret.first && ret.second < bret.second + 1)){
ret = {false, bret.second + 1};
}
}
board[ay][ax] = 1;
if(ret.second == -1) return {false, 0};
return ret;
}
int solution(vector<vector<int>> board, vector<int> aloc, vector<int> bloc) {
int ans = -1;
int height = board.size(), width = board[0].size();
ans = aturn(board, aloc[1], aloc[0], bloc[1], bloc[0]).second;
return ans;
}
결과
이전과는 다르게 이번에는 2차 코딩테스트까지 풀어보았다. 간단한 CS문제와 휴리스틱 스타일의 문제가 출제되었다.
