mojo's Blog
2023 KAKAO BLIND RECRUITMENT 문제 리뷰 본문
1. 개인정보 수집 유효기간
문제 링크: 코딩테스트 연습 - 개인정보 수집 유효기간 | 프로그래머스 스쿨 (programmers.co.kr)
단순 구현문제이다.
구현하면서 조심해야 할 부분은 privacies 의 길이가 최대 100 까지 주어진다는 점이다.
연도, 월, 일을 privacy 값에 맞게 조정해준 후 today와 비교하여 파기해야 할 개인정보를 구하면 된다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
char term_info[26];
int answer_info[100];
void set_term_info(const char* terms[], size_t terms_len) {
for (size_t i = 0; i < terms_len; i++)
term_info[terms[i][0] - 'A'] = atoi(terms[i] + 2);
}
int get_time(int year, int month, int day) {
return year * 10000 + month * 100 + day;
}
int* solution(const char* today, const char* terms[], size_t terms_len,
const char* privacies[], size_t privacies_len) {
int* answer;
int today_year, today_month, today_day;
size_t answer_len;
today_year = atoi(today);
today_month = atoi(today + 5);
today_day = atoi(today + 8);
answer_len = 0;
set_term_info(terms, terms_len);
for (size_t i = 0; i < privacies_len; i++) {
int privacy_year = atoi(privacies[i]);
int privacy_month = atoi(privacies[i] + 5);
int privacy_day = atoi(privacies[i] + 8);
char privacy_term = privacies[i][11];
privacy_month += term_info[privacy_term - 'A'];
while (privacy_month > 12) {
privacy_year += 1;
privacy_month -= 12;
}
if (get_time(today_year, today_month, today_day)
>= get_time(privacy_year, privacy_month, privacy_day))
answer_info[answer_len++] = i + 1;
}
answer = (int *)malloc(sizeof(int) * answer_len);
for (size_t i = 0; i < answer_len; i++) {
answer[i] = answer_info[i];
}
return answer;
}
2. 택배 배달과 수거하기
문제 링크: 코딩테스트 연습 - 택배 배달과 수거하기 | 프로그래머스 스쿨 (programmers.co.kr)
그리디 문제이다.
이 문제는 실제로 코딩테스트때 생각을 오래해서 해결한 문제이다.
배달/수거 를 각각 뒤에서부터 살피면서 0이 아닌 값이 나올 때 부터 cap 개수만큼 배달/수거 를 처리해주면서,
최초로 0이 아닌 값의 인덱스를 통해 배달에 대한 왕복 거리, 수거에 대한 왕복 거리를 구할 수 있다.
그 중에서 왕복 거리가 더 큰 값을 계속해서 누적한다면 답이 나온다.
문제에 주어진 예시를 가지고 생각해보자.
cap = 4, n = 5
deliveries = [1, 0, 3, 1, 2]
pickups = [0, 3, 0, 4, 0]
(1) deliveries 는 인덱스 4에 상자가 존재하므로 배달에 대한 왕복 거리는 10((4 + 1) * 2)이다.
그리고 cap 개수만큼 배달을 처리하면 [1, 0, 2, 0, 0] 이 되고 종료한다.
pickups 는 인덱스 3에 상자가 존재하므로 수거에 대한 왕복 거리는 8((3 + 1) * 2)이다.
그리고 cap 개수만큼 수거를 처리하면 [0, 3, 0, 0, 0] 이 되고 종료한다.
배달에 대한 왕복 거리가 더 크므로 총 왕복 거리는 10이다.
(2) deliveries 는 인덱스 2에 상자가 존재하므로 배달에 대한 왕복 거리는 6((2 + 1) * 2)이다.
그리고 (cap - 1)개수만큼 배달을 처리하면 [0, 0, 0, 0, 0] 이 되고 종료한다.
pickups 는 인덱스 1에 상자가 존재하므로 수거에 대한 왕복 거리는 4((1 + 1) * 2)이다.
그리고 (cap - 1)개수만큼 수거를 처리하면 [0, 0, 0, 0, 0] 이 되고 종료한다.
이번에도 배달에 대한 왕복 거리가 더 크므로 총 왕복 거리는 16이다.
위와 같은 방식으로 총 왕복 거리를 계산할 수 있다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
long long get_dist(int cap, int n, int arr[], int* total, int* idx) {
int dist = 0;
int cnt = 0;
for (int i = *idx; i >= 0; i--) {
*idx = i;
if (arr[i]) {
dist = dist > 2 * (i + 1) ? dist : 2 * (i + 1);
if (cnt + arr[i] > cap) {
arr[i] -= (cap - cnt);
cnt = cap;
break;
}
else {
cnt += arr[i];
arr[i] = 0;
}
}
}
*total -= cnt;
return (long long)dist;
}
long long solution(int cap, int n, int deliveries[], size_t deliveries_len,
int pickups[], size_t pickups_len) {
long long answer = 0;
int cur_delivery, cur_pickup;
int delivery_idx, pickup_idx;
cur_delivery = cur_pickup = 0;
for (int i = 0; i < n; i++)
cur_delivery += deliveries[i];
for (int i = 0; i < n; i++)
cur_pickup += pickups[i];
delivery_idx = pickup_idx = n - 1;
while (cur_delivery || cur_pickup) {
long long delivery_dist = 0;
long long pickup_dist = 0;
delivery_dist = get_dist(cap, n, deliveries, &cur_delivery, &delivery_idx);
pickup_dist = get_dist(cap, n, pickups, &cur_pickup, &pickup_idx);
answer += delivery_dist > pickup_dist ? delivery_dist : pickup_dist;
}
return answer;
}
3. 이모티콘 할인행사
문제 링크: 코딩테스트 연습 - 이모티콘 할인행사 | 프로그래머스 스쿨 (programmers.co.kr)
깊이우선탐색 문제이다.
문제에서 요구하는 것은 다음과 같다.
(1) 이모티콘 플러스 서비스 가입자를 최대로 늘린다.
(2) 이모티콘 판매액을 최대한 늘린다.
(1) 번 목표가 우선이며, (2) 번 목표가 그 다음이다.
보자마자 우선순위 큐 를 떠올릴 수 있다.
그리고 이모티콘 할인 행사는 다음과 같은 방식으로 진행된다고 한다.
- n명의 사용자들에게 이모티콘 m개를 할인하여 판매한다.
- 이모티콘마다 할인율은 다르며, 10%, 20%, 30%, 40% 중 하나로 설정된다.
이모티콘 m개를 총 4가지 할인율을 적용하여 판매하기 위해선 DFS 를 떠올릴 수 있다.
시간 복잡도는 O(\(4^{m}\)) 으로 구현할 수 있겠다.
사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스를 가입한다고 한다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매한다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면,
이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다.
이모티콘의 할인율이 결정될 때(dfs 를 통해), 위 조건에 맞게 서비스 가입자 및 판매액을 구한다.
그리고 우선순위 큐에 {서비스 가입자, 판매액} 을 push 한다.
최종적으로 dfs 가 종료되면 top 에 있는 {서비스 가입자, 판매액} 이 정답이 된다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct priority_queue {
int member;
int sale_cost;
} PQ;
PQ pq[16385];
int emoticons_rate[7];
bool check(PQ x, PQ y) {
if (x.member == y.member)
return x.sale_cost > y.sale_cost;
return x.member > y.member;
}
void add(int member, int sale_cost) {
static int p_cnt = 1;
int cur_idx, parent_idx;
PQ tmp;
pq[p_cnt].member = member;
pq[p_cnt].sale_cost = sale_cost;
cur_idx = p_cnt;
p_cnt++;
while (cur_idx) {
parent_idx = cur_idx / 2;
if (check(pq[cur_idx], pq[parent_idx])) {
tmp = pq[parent_idx];
pq[parent_idx] = pq[cur_idx];
pq[cur_idx] = tmp;
cur_idx = parent_idx;
}
else break;
}
}
void dfs(int idx, int** users, int users_len, int emoticons[], size_t emoticons_len) {
if (idx == emoticons_len) {
int member = 0;
int sale_cost = 0;
for (int i = 0; i < users_len; i++) {
int user_rate = users[i][0];
int user_price = users[i][1];
int cur_price = 0;
for (int j = 0; j < emoticons_len; j++) {
if (user_rate > emoticons_rate[j])
continue;
cur_price += emoticons[j] * (100 - emoticons_rate[j]) / 100;
}
if (cur_price >= user_price)
member++;
else
sale_cost += cur_price;
}
add(member, sale_cost);
return;
}
for (int i = 10; i <= 40; i += 10) {
emoticons_rate[idx] = i;
dfs(idx + 1, users, users_len, emoticons, emoticons_len);
}
}
int* solution(int** users, size_t users_rows, size_t users_cols, int emoticons[], size_t emoticons_len) {
int* answer = (int*)malloc(sizeof(int) * 2);
dfs(0, users, users_rows, emoticons, emoticons_len);
answer[0] = pq[0].member, answer[1] = pq[0].sale_cost;
return answer;
}
4. 표현 가능한 이진트리
문제 링크: 코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)
트리 문제이다.
숫자가 주어지면 이진트리를 만들 수 있는지 묻는 문제이다.
핵심은 더미 노드의 자식 노드로는 오직 더미 노드만 가능 하며 실제 노드가 추가되서는 안된다.
이 문제는 다음과 같이 접근하였다.
(1) 숫자를 이진수로 나타낸다. (\( 63 ~> 111111_{2} \))
(2) 이진수의 길이가 \(2^{i} - 1\) 이 되도록 0을 추가해준다. (i는 양수)
- 이진 트리로 만들 수 있으면 결국 포화 이진 트리 이기 때문
(3) root 노드로부터 시작하여 leaf 노드까지 이동하여 이진 트리를 만들 수 있는지 탐색한다.
- 실제 노드인 경우(1) : 부모 노드가 더미 노드이면 false 반환, 그 외에 true 반환
- 더미 노드인 경우(0) : 자식으로 이동할 때, 함수 dummy 인자에 true 값을 넣음
위 과정을 통해 이진트리를 만들 수 있는지를 판단할 수 있다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int binary[64];
int binary_len;
void make_binary(long long number) {
int idx = 0;
while (number) {
binary[idx++] = number % 2;
number /= 2;
}
for (int len = 1; len < 64; len = 2 * len + 1) {
if (idx <= len) {
binary_len = len;
break;
}
}
for (int i = idx; i < binary_len; i++)
binary[i] = 0;
}
bool is_binary_tree(int left, int right, bool dummy) {
if (left == right) {
if (binary[left] && dummy)
return false;
return true;
}
else {
int mid = (left + right) / 2;
if (binary[mid]) {
if (dummy)
return false;
return is_binary_tree(left, mid - 1, dummy) && is_binary_tree(mid + 1, right, dummy);
}
return is_binary_tree(left, mid - 1, true) && is_binary_tree(mid + 1, right, true);
}
}
int* solution(long long numbers[], size_t numbers_len) {
int* answer = (int*)malloc(sizeof(int) * numbers_len);
for (size_t i = 0; i < numbers_len; i++) {
make_binary(numbers[i]);
if (is_binary_tree(0, binary_len - 1, false))
answer[i] = 1;
else
answer[i] = 0;
}
return answer;
}
5. 표 병합
문제 링크: 코딩테스트 연습 - 표 병합 | 프로그래머스 스쿨 (programmers.co.kr)
유니온 파인드 문제이다.
문제에서 요구하는 명령어들을 자세히 살펴보자
(1) UPDATE r c value
말 그대로 (r, c) 위치의 셀을 선택해서 value로 바꾸면 된다.
그러나 merge가 된 경우에는 (r, c) 가 아닌 (r, c) 의 최상단 부모인 위치의 셀을 선택해서 value로 바꿔주면 된다.
(2) UPDATE value1 value2
문자열 value1 을 가지고 있는 셀을 전부 찾아서 value2 로 바꿔주면 된다.
(3) MERGE r1 c1 r2 c2
(r1, c1) 위치와 (r2, c2) 위치를 union 해주면 된다.
작업 편의성을 위해 (r, c) 를 50 * (r - 1) + c 로 변환하였다.
(4) UNMERGE r c
이 부분이 골치아팠던 명령어 중 하나이다.
unmerge 하는 과정을 단순히 생각해보면 (r, c) 의 최상단 부모와 임의의 셀의 최상단 부모가 같을 경우에
임의의 셀의 부모를 자기 자신을 가르키도록 해주면 될 것 같다.
하지만 반복문을 돌면서 위 과정대로 진행한다면 최상단 부모가 의도하지 못한 결과가 나타나게 된다.
예를 들어 생각해보자.
1번 노드부터 5번 노드까지 최상단 부모 노드는 1번 노드로 되어있다.
unmerge 할 노드를 1이라고 할 때, 1번 노드부터 5번 노드까지 작업을 해주어야 한다.
2 번 노드는 현재 최상단 부모 노드가 1번 노드이므로 unmerge 대상자다.
따라서 아래와 같이 된다.
반면에 3번 노드는 현재 최상단 부모 노드가 2번 노드이므로 unmerge 대상자가 아니다.
즉, 위와 같은 방식으로 unmerge 하지 않고 최상단 부모 노드와 같은 노드들을 담아두고 담아둔 노드들을
가지고 unmerge 작업을 해주어야 한다.
(5) PRINT r c
(r, c) 위치의 최상단 부모 노드의 셀을 찾아서 value 를 출력하면 된다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
char* cell[2501];
int parent[2501];
void initialize() {
for (int i = 1; i <= 2500; i++) {
parent[i] = i;
cell[i] = NULL;
}
}
int get_space_cnt(char* command) {
int space = 0;
while (*command) {
if (*command == ' ')
space++;
command++;
}
return space;
}
int get_parent(int cur) {
if (cur == parent[cur])
return cur;
return (parent[cur] = get_parent(parent[cur]));
}
void set_union(int x, int y) {
x = get_parent(x);
y = get_parent(y);
if (cell[x] && cell[y])
parent[y] = x;
else if (cell[y])
parent[x] = y;
else
parent[y] = x;
}
int p(int r, int c) {
return 50 * (r - 1) + c;
}
void update_value(char* command) {
char* value;
char* change;
char* ptr = strtok(command + 7, " ");
value = ptr; ptr = strtok(NULL, " ");
change = ptr;
for (int i = 1; i <= 2500; i++) {
if (cell[i] && !strcmp(cell[i], value))
cell[i] = change;
}
}
void update_cell(char* command) {
int r, c;
char* value;
char* ptr = strtok(command + 7, " ");
r = atoi(ptr); ptr = strtok(NULL, " ");
c = atoi(ptr); ptr = strtok(NULL, " ");
value = ptr;
cell[get_parent(p(r, c))] = value;
}
void merge_cell(char* command) {
int r1, c1, r2, c2;
char* ptr = strtok(command + 6, " ");
r1 = atoi(ptr); ptr = strtok(NULL, " ");
c1 = atoi(ptr); ptr = strtok(NULL, " ");
r2 = atoi(ptr); ptr = strtok(NULL, " ");
c2 = atoi(ptr);
set_union(p(r1, c1), p(r2, c2));
}
void unmerge_cell(char* command) {
int r, c, cnt;
int merge_info[2501];
char* value;
char* ptr = strtok(command + 8, " ");
cnt = 0;
r = atoi(ptr); ptr = strtok(NULL, " ");
c = atoi(ptr);
value = cell[get_parent(p(r, c))];
for (int i = 1; i <= 2500; i++) {
if (get_parent(i) == get_parent(p(r, c)))
merge_info[cnt++] = i;
}
for (int i = 0; i < cnt; i++) {
parent[merge_info[i]] = merge_info[i];
cell[merge_info[i]] = NULL;
}
cell[get_parent(p(r, c))] = value;
}
char* print_cell(char* command) {
int r, c;
char* ptr = strtok(command + 6, " ");
r = atoi(ptr); ptr = strtok(NULL, " ");
c = atoi(ptr);
return cell[get_parent(p(r, c))];
}
char** solution(const char* commands[], size_t commands_len) {
char** answer;
char* word;
int answer_len = 0;
for (size_t i = 0; i < commands_len; i++) {
if (commands[i][0] == 'P')
answer_len++;
}
answer = (char **)malloc(sizeof(char *) * (answer_len + 1));
initialize();
for (size_t i = 0, j = 0; i < commands_len; i++) {
char* command = commands[i];
if (command[0] == 'U' && command[1] == 'P') {
// UPDATE value1 value2
if (get_space_cnt(command) == 2) {
update_value(command);
}
// UPDATE r c value
else {
update_cell(command);
}
}
// MERGE r1 c1 r2 c2
else if (command[0] == 'M') {
merge_cell(command);
}
// UNMERGE r c
else if (command[0] == 'U' && command[1] == 'N') {
unmerge_cell(command);
}
// PRINT r c
else if (command[0] == 'P') {
word = print_cell(command);
if (word) {
answer[j] = (char *)malloc(strlen(word) + 1);
answer[j] = word;
}
else {
answer[j] = (char *)malloc(6);
answer[j] = "EMPTY";
}
j++;
}
}
answer[answer_len] = NULL;
return answer;
}
6. 미로 탈출 명령어
문제 링크: 코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)
너비 우선 탐색(?) 문제이다.
미로에서 탈출한 경로를 문자열로 나타낼 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.
사전 순으로 빠르게 탈출하기 위해 우선순위 큐 를 이용하였다. (좋은 풀이는 아닌거 같다...)
우선순위 큐에 담길 정보는 다음과 같다.
(1) direction : 방향에 대한 인덱스
(2) dist : (x, y) 까지 이동한 거리
(3) (x, y) : 현재 이동한 지점
우선순위는 다음과 같이 결정하였다.
(1) direction 값을 최대로 한다. (3 - d, 2 - u, 1 - r, 0 - l)
(2) direction 이 동일할 경우 dist 값을 최대로 한다.
(3) dist 값도 동일할 경우 x 값을 최대로 한다.
(4) x 값도 동일할 경우 y 값을 최대로 한다.
우선순위 큐를 이용하여 너비 우선 탐색을 수행하면서 거리가 K 일때 도착 지점에 온 경우 이전에 이동했던 정보를
역추적하여 문자열을 만들면 된다.
너비 우선 탐색이 끝나면 도착 지점에 도달하지 못한 경우이므로 "impossible" 을 반환하면 된다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct point {
int x;
int y;
} Point;
typedef struct pq {
int direction;
int dist;
Point p;
} PQ;
int N, M, K;
int s_x, s_y, e_x, e_y;
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, 1, -1, 0 };
bool visited[51][51][2501];
Point child[51][51][2501];
PQ pq[100001];
int pq_cnt;
bool check(PQ x, PQ y) {
if (x.direction == y.direction) {
if (x.dist == y.dist) {
if (x.p.x == y.p.x) {
return x.p.y > y.p.y;
}
return x.p.x > y.p.x;
}
return x.dist > y.dist;
}
return x.direction > y.direction;
}
void add(int direction, int dist, Point p) {
int cur_idx, parent_idx;
PQ tmp;
cur_idx = ++pq_cnt;
pq[pq_cnt].direction = direction;
pq[pq_cnt].dist = dist;
pq[pq_cnt].p = p;
while (cur_idx != 1) {
parent_idx = cur_idx / 2;
if (check(pq[cur_idx], pq[parent_idx])) {
tmp = pq[parent_idx];
pq[parent_idx] = pq[cur_idx];
pq[cur_idx] = tmp;
cur_idx = parent_idx;
}
else break;
}
}
PQ pop() {
int cur_idx, child_idx;
PQ ret, tmp;
ret = pq[1];
pq[1] = pq[pq_cnt--];
cur_idx = 1;
while (cur_idx <= pq_cnt / 2) {
if (check(pq[2 * cur_idx], pq[2 * cur_idx + 1]))
child_idx = 2 * cur_idx;
else
child_idx = 2 * cur_idx + 1;
if (check(pq[child_idx], pq[cur_idx])) {
tmp = pq[child_idx];
pq[child_idx] = pq[cur_idx];
pq[cur_idx] = tmp;
cur_idx = child_idx;
}
else break;
}
return ret;
}
bool is_in(int x, int y) {
return x >= 1 && x <= N && y >= 1 && y <= M;
}
char* get_result(Point cur_p) {
int dist = K;
Point child_p;
char* ret = (char*)malloc(K + 1);
ret[K--] = '\0';
while (dist) {
child_p = child[cur_p.x][cur_p.y][dist];
if (cur_p.x == child_p.x) {
if (cur_p.y - child_p.y == 1)
ret[K--] = 'r';
else
ret[K--] = 'l';
}
else if (cur_p.y == child_p.y) {
if (cur_p.x - child_p.x == 1)
ret[K--] = 'd';
else
ret[K--] = 'u';
}
cur_p = child_p;
dist--;
}
return ret;
}
char* bfs() {
PQ info;
Point cur_p, next_p;
char* ret;
cur_p.x = s_x, cur_p.y = s_y;
add(0, 0, cur_p);
visited[s_x][s_y][0] = true;
while (pq_cnt) {
info = pop();
cur_p = info.p;
if (info.dist == K) {
if (cur_p.x == e_x && cur_p.y == e_y)
return get_result(cur_p);
continue;
}
for (int i = 0; i < 4; i++) {
next_p.x = cur_p.x + dx[i];
next_p.y = cur_p.y + dy[i];
if (is_in(next_p.x, next_p.y) && !visited[next_p.x][next_p.y][info.dist + 1]) {
visited[next_p.x][next_p.y][info.dist + 1] = true;
child[next_p.x][next_p.y][info.dist + 1] = cur_p;
add(i, info.dist + 1, next_p);
}
}
}
ret = (char *)malloc(11);
return (ret = "impossible");
}
char* solution(int n, int m, int x, int y, int r, int c, int k) {
char* answer;
N = n, M = m, K = k;
s_x = x, s_y = y, e_x = r, e_y = c;
answer = bfs();
return answer;
}
7. 1, 2, 3 떨어트리기
문제 링크: 코딩테스트 연습 - 1,2,3 떨어트리기 | 프로그래머스 스쿨 (programmers.co.kr)
트리 문제이다.
게임 규칙을 살펴보면서 구현을 어떻게 해야할지 파악해보자.
(1) 루트 노드에 숫자 1, 2, 3 중 하나를 떨어뜨린다.
말 그대로 루트 노드에 숫자를 아무거나 하나 떨어뜨려도 된다는 것을 알 수 있다.
(2) 숫자는 길인 간선을 따라 리프 노드까지 떨어진다.
리프노드에 숫자의 개수를 cnt 라고 해보자.
그러면 숫자의 합을 sum 이라고 할 때, cnt <= sum <= 3 * cnt 조건을 만족할 수 있음을 유추할 수 있다.
(3) 숫자가 리프 노드에 도착하면, 숫자가 지나간 각 노드는 현재 길로 연결된 자식 노드 다음으로 번호가 큰 자식 노드
를 가리키는 간선을 새로운 길로 설정하고 기존의 길은 끊는다.
- 만약 현재 길로 연결된 노드의 번호가 가장 크면, 번호가 가장 작은 노드 를 가리키는 간선을 길로 설정한다.
- 노드의 간선이 하나라면 계속 하나의 간선을 길로 설정한다.
여기서 할 수 있는 작업으로는 현재 노드의 자식 노드들이 여러 개일때, 오름차순으로 정렬되도록 해야한다.
(4) 원하는 만큼 계속해서 루트 노드에 숫자를 떨어트릴 수 있다.
- 단, 앞서 떨어트린 숫자가 리프 노드까지 떨어진 후에 새로운 숫자를 떨어트려야 한다.
이 규칙을 잘못 이해해서 삽질을 많이 했는데 새로운 숫자를 떨어트린다는 의미가 이전에 떨어트린 숫자를 다시
떨어트리는 것이 아니라 새로운 숫자를 떨어트리라는 의미다.
즉, 이전에 떨어트린 숫자와 새로운 숫자가 같은 값이 나와도 상관 없다 는 것이다.
게임의 목표는 리프 노드에 쌓인 숫자의 합이 target 에서 가르키는 값과 같게 만들어야 한다.
이때, target 대로 리프 노드에 쌓인 숫자의 합을 맞추기 위해 숫자를 떨어트리는 모든 경우 중 가장 적은 숫자를
사용하며 그중 사전 순으로 가장 빠른 경우를 찾아야 한다.
문제 접근 방법은 다음과 같다.
(1) 트리를 설계하고 자식 노드들이 오름차순이 되도록 정렬한다.
그리고 leaf 노드들을 dfs 를 통해 자식 노드가 없을 때까지 이동하여 해당 노드들을 담아준다.
(2) 초기 경로를 설계한다. (모든 부모 노드는 자식 노드 중 가장 번호가 작은 노드를 가르키도록 함)
이동이 가능한 지 여부를 판단할 수 있도록 2차원 배열 path를 통해 path[cur][next] 값이 true 이면
이동할 수 있도록 하였다.
(3) 게임 규칙 (4)에 의하면, 원하는 만큼 계속 숫자를 떨어트릴 수 있으므로 최대 10,000번 떨어트릴 수 있도록 하였다.
최악의 경우로 1번 노드에 자식 노드 [2, 3, ..., 99, 100] 이 연결되어 있다하고 target 값이 전부 100 이라 해보자.
이 경우에 대략 10,000번 보다는 적은 것이 확실하기 때문에 임의로 10,000번 떨어트리도록 했다.
(4) 초기 경로로부터 얻은 리프 노드를 시작으로 하여 계속 새로운 리프 노드를 방문하게 될 것이다.
리프 노드의 방문 횟수(숫자 개수)를 1씩 증가시키고 게임 규칙 (2)에 의하여 다음과 같은 조건을 통해
target 값을 만족하는지 확인할 수 있다.
방문 횟수를 v, target 값을 t 라고 할 때, v <= t <= 3 * v 조건을 만족하면 만들 수 있다.
이러한 조건이 모든 리프 노드에서 만족할 경우, 루트 노드에 떨어트린 숫자의 개수를 반환한다.
10,000번을 수행했음에도 만족하지 못하면, -1을 반환한다.
(5) target 대로 리프 노드에 쌓인 숫자의 합을 맞출 수 있으면 리프 노드의 방문 횟수(숫자 개수) 만큼 사전 순으로
가장 빠르게 되도록 1, 2, 3 을 저장해둔다.
그리고 초기 경로를 재설계하고 루트 노드에 떨어트린 숫자의 개수만큼 다시 리프 노드를 이동하여
해당 리프 노드의 저장된 숫자를 꺼내와서 결과에 담아주면 된다.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct edge {
int node;
struct edge* next;
} Edge;
typedef struct graph {
int edge_cnt;
struct edge* edge;
} Graph;
typedef struct leaf {
int node;
struct leaf* next;
} Leaf;
Graph graph[101];
Edge edge[101];
Leaf* leaf, dummy[101];
bool path[101][101];
int* number_info[101];
int visited[101];
int leaf_cnt;
Edge* get_edge(int node) {
static int cnt = 0;
edge[cnt].node = node;
edge[cnt].next = NULL;
return &edge[cnt++];
}
Leaf* get_leaf(int node) {
static int cnt = 0;
dummy[cnt].node = node;
dummy[cnt].next = NULL;
return &dummy[cnt++];
}
void push_node(int cur, int node) {
Edge* tmp;
graph[cur].edge_cnt++;
if (!graph[cur].edge)
graph[cur].edge = get_edge(node);
else {
tmp = get_edge(node);
tmp->next = graph[cur].edge;
graph[cur].edge = tmp;
}
}
void push_leaf(int node) {
Leaf* tmp;
leaf_cnt++;
if (!leaf)
leaf = get_leaf(node);
else {
tmp = get_leaf(node);
tmp->next = leaf;
leaf = tmp;
}
}
void initialize(int node_cnt) {
leaf = NULL;
for (int i = 1; i <= node_cnt; i++) {
graph[i].edge_cnt = 0;
graph[i].edge = NULL;
}
}
void set_leafs(int cur) {
if (!graph[cur].edge_cnt) {
push_leaf(cur);
return;
}
for (Edge* e = graph[cur].edge; e; e = e->next)
set_leafs(e->node);
}
int compare(const void* x, const void* y) {
int num1 = *(int*)x;
int num2 = *(int*)y;
if (num1 < num2)
return -1;
if (num1 > num2)
return 1;
return 0;
}
void sort_graph(int node_cnt) {
int node[100];
int edge_cnt;
Edge* e;
for (int i = 1; i <= node_cnt; i++) {
if (!graph[i].edge_cnt)
continue;
edge_cnt = 0;
e = graph[i].edge;
while (e) {
node[edge_cnt++] = e->node;
e = e->next;
}
qsort(node, edge_cnt, sizeof(int), compare);
edge_cnt = 0;
e = graph[i].edge;
while (e) {
e->node = node[edge_cnt++];
e = e->next;
}
}
}
void init_path(int node_cnt) {
for (int i = 1; i <= node_cnt; i++)
for (int j = 1; j <= node_cnt; j++)
path[i][j] = false;
}
void set_path(int cur) {
if (!graph[cur].edge_cnt)
return;
int next;
bool first = true;
for (Edge* e = graph[cur].edge; e; e = e->next) {
next = e->node;
if (first) {
path[cur][next] = true;
first = false;
}
set_path(next);
}
}
int dfs(int cur) {
if (!graph[cur].edge_cnt)
return cur;
int next, leaf_node;
Edge* e;
for (e = graph[cur].edge; e; e = e->next) {
next = e->node;
if (path[cur][next]) {
path[cur][next] = false;
leaf_node = dfs(next);
if (e->next)
next = e->next->node;
else
next = graph[cur].edge->node;
path[cur][next] = true;
return leaf_node;
}
}
}
int drop_number(int target[], int target_len) {
int cur, cnt;
int drop_cnt = 0;
init_path(target_len);
set_path(1);
while (drop_cnt++ <= 10000) {
cur = dfs(1);
visited[cur]++;
cnt = 0;
for (Leaf* l = leaf; l; l = l->next) {
int node = l->node;
if (visited[node] <= target[node - 1]
&& target[node - 1] <= 3 * visited[node])
cnt++;
}
if (cnt == leaf_cnt)
return drop_cnt;
}
return -1;
}
void set_number_info(int leaf_node, int target[], int target_len) {
int cnt_1, cnt_2, cnt_3;
int num = target[leaf_node - 1];
int idx = 0;
number_info[leaf_node] = (int*)malloc(sizeof(int) * visited[leaf_node]);
cnt_1 = cnt_2 = cnt_3 = 0;
while (visited[leaf_node]) {
if (num - 1 <= 3 * (visited[leaf_node] - 1))
cnt_1++, num -= 1;
else if (num - 2 <= 3 * (visited[leaf_node] - 1))
cnt_2++, num -= 2;
else
cnt_3++, num -= 3;
visited[leaf_node]--;
}
while (cnt_1--)
number_info[leaf_node][idx++] = 1;
while (cnt_2--)
number_info[leaf_node][idx++] = 2;
while (cnt_3--)
number_info[leaf_node][idx++] = 3;
}
int* set_numbers(int drop_cnt, int target[], int target_len) {
int* ret;
int leaf_node, num;
int idx = 0;
init_path(target_len);
set_path(1);
for (Leaf* l = leaf; l; l = l->next) {
leaf_node = l->node;
set_number_info(leaf_node, target, target_len);
}
ret = (int*)malloc(sizeof(int) * drop_cnt);
while (drop_cnt--) {
leaf_node = dfs(1);
num = visited[leaf_node];
ret[idx++] = number_info[leaf_node][num];
visited[leaf_node]++;
}
return ret;
}
int* solution(int** edges, size_t edges_rows, size_t edges_cols,
int target[], size_t target_len) {
int* answer;
int from, to;
int drop_cnt;
initialize(target_len);
for (size_t i = 0; i < edges_rows; i++) {
from = edges[i][0], to = edges[i][1];
push_node(from, to);
}
sort_graph(target_len);
set_leafs(1);
if ((drop_cnt = drop_number(target, target_len)) != -1)
answer = set_numbers(drop_cnt, target, target_len);
else {
answer = (int*)malloc(sizeof(int));
answer[0] = -1;
}
return answer;
}
2023 카카오 블라인드 공채 후기
- 1차 코딩테스트 (합)
7 번 문제를 제외한 나머지 문제들을 간신히 풀어냈고 그 결과 합격 하였다.
- 2차 코딩테스트 (합)
필기 시험과 코딩테스트가 있었다.
필기 시험은 자료구조, 알고리즘, 네트워크, 데이터베이스, 운영체제 에서 출제되었다.
특히 2차 코테는 기존 유형과 달라서 시간관계상 api 다루는 부분만 준비하였다.
점수가 좋지는 않았지만 합격 하였다. (500점대)
- 1차 면접 (불합)
면접은 대략 60분 가까이 진행이 되었다.
면접관은 2명으로 1 : 2 로 진행하였으며, 면접 진행 흐름은 다음과 같다.
(1) 2차 코딩테스트 리뷰
화면에 코드를 띄우지 않고 어떻게 구현했는지 설명해야 했다.
작성했던 코드들을 떠올리면서 코드 플로우를 설명하고, 어떤 부분에서 점수가 낮게 나왔는지를 설명하며
"이런식으로 개선하면 더 좋은 점수를 받을 수 있겠다" 와 같이 추가로 설명하였다.
(2) cs 질문
이번 2차 코딩테스트 문제는 단편화를 연상할 수 있는 문제였다.
따라서 운영체제에서 단편화, 페이징에 대한 질문들을 받았다.
네트워크 질문으로는 OSI 7계층, TCP와 UDP 차이에 대한 질문들을 받았다.
그 외의 cs 질문은 없었던 것 같다.
(3) 직무 관심도
직무 관련해서 여러 질문을 해주셨지만 단 하나도 답하지 못하였다.
또한, 인턴십을 지원할 때는 프로그래밍 분야를 지원했지만 이번에는 시스템 엔지니어링을 지원했기에
왜 직무 분야가 변경되었는지 질문도 하셨다.
여기서 불합격의 기운을 느낄 수 있었다.
(4) 자기소개서 검증
자기소개서에 작성했던 프로젝트나 경험들에 대한 검증 시간을 가졌다.
결과는 불합격 이였다.
불합격의 원인은 직무 관심도가 현저히 떨어졌다는 것이였다.
하지만 면접 전형까지 가서 면접관분들의 피드백을 들을 수 있어서 좋은 기회였다.
'프로그래머스' 카테고리의 다른 글
2021 카카오 인턴십 문제 리뷰 (0) | 2022.04.28 |
---|---|
2021 KAKAO BLIND RECRUITMENT 문제 리뷰 (0) | 2022.03.01 |
2022 KAKAO BLIND RECRUITMENT 문제 리뷰 (0) | 2022.01.22 |