2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트가 지난 9월 24일에 열렸습니다. 올해는 효율성 테스트 문제없이 7 문제가 출제되었으며, 난이도는 작년과 비슷했습니다. 문제는 쉬운 난이도부터 어려운 난이도 순으로 배치되었고, 올해 문제의 특징은 특별한 알고리즘을 사용하지 않아도 풀 수 있다는 점입니다.
그럼 풀이를 진행하겠습니다.
문제 1 – 개인정보 수집 유효기간
각 개인 정보가 수집된 날과 약관 종류로부터 보관 가능 날짜를 구하고, 오늘 날짜가 보관 가능 날짜를 지났는지를 구하면 되는 문제입니다. 개인 정보의 유효기간은 해시 테이블 등의 방법으로 구할 수 있습니다.
날짜를 비교할 때 YYYY.MM.DD 형태 그대로 비교해도 되지만, 2000년 1월 1일로부터 며칠이 흘렀는지를 계산하면 정수 형태로 쉽게 비교할 수 있습니다.
문제 2 – 택배 배달과 수거하기
이 문제는 그리디 전략(Greedy strategy)으로 해결 가능한 문제입니다. 이 문제를 해결하기 위한 그리디 전략은 다음과 같습니다.
- 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다.
- 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다.
- 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 수거합니다.
위에서 설명한 그리디 전략은 스택 두 개를 활용하면 쉽게 구현 가능합니다. 가장 먼 집으로 이동할 때는 배달만 하고 돌아올 때는 수거만 하므로, 한 번에 배달 및 수거 가능한 택배 개수는 트럭에 실을 수 있는 택배 상자의 최대 개수(cap)와 동일합니다.
- 집 번호와 해당 집에 배달할 택배 개수를 집 번호가 작은 순서대로 배달 스택에 담습니다.
- 집 번호와 해당 집에 수거할 빈 택배 개수를 집 번호가 작은 순서대로 수거 스택에 담습니다.
- 배달 스택에서 가장 위에 위치한 원소의 집 번호와 수거 스택에서 가장 위에 위치한 원소의 집 번호를 비교해 큰 값의 두 배만큼 answer에 더합니다. 이때, 두 배를 더하는 이유는 트럭이 물류창고부터 가장 먼 집까지 왕복하기 때문입니다.
- 이번에 배달 가능한 개수가 0이 되거나 배달 스택이 빌 때까지 배달 스택에서 남은 배달을 처리합니다.
- 이번에 수거 가능한 개수가 0이 되거나 수거 스택이 빌 때까지 수거 스택에서 남은 수거를 처리합니다.
- 배달 스택과 수거 스택이 모두 빌 때까지 3, 4, 5 과정을 반복합니다.
배달과 수거 스택에서 남은 배달 및 수거를 처리하는 방법
배달 스택에서 가장 위에 위치한 원소는 배달할 택배가 남아있는 집 중 가장 멀리 있는 집입니다.
이번에 배달 가능한 개수는 cap으로 시작해, 배달 스택에서 꺼내는 순서대로 배달할 택배 개수만큼 감소시킵니다. 만약 이번에 배달 가능한 개수가 배달할 택배 개수보다 작다면, 배달할 택배 개수를 이번에 배달 가능한 개수만큼 감소시킨 뒤 다시 배달 스택에 담습니다.
수거 스택에서도 이번에 수거 가능한 개수를 cap으로 시작하여 배달 스택과 같은 방법으로 처리하면 됩니다.
각 집에서 배달 및 수거할 택배 상자의 최대 개수와, 트럭에 실을 수 있는 택배 상자의 최대 개수(cap)는 모두 50 이하입니다. 이를 상수 취급했을 때, 위 알고리즘의 시간복잡도는 O(n) 입니다. (n = 배달 및 수거할 집의 개수)
다른 방법
그리디 전략을 쓰지만 스택을 사용하지 않는 풀이 방법도 있습니다. 가장 먼 집부터 배달 상자 수와 수거 상자 수를 각각 누적 합을 구한 후, 둘 중에 하나가 cap을 넘는다면 누적한 배달 상자 수와 수거 상자 수를 각각 cap만큼 비우면서 이동한 거리를 answer에 더하는 방법입니다. 여기서 이동한 거리를 구하기 위해 상자가 비워질 때의 위치를 저장해 둡니다. cap만큼 비우면서 누적 배달 상자 수 또는 수거 상자 수가 음수가 될 수 있습니다. 누적 상자 수가 cap만큼 덜 채워졌을 경우로, 다음 집의 상자를 미리 배달하거나 수거하는 효과를 가져서 음수가 되어도 괜찮습니다.
문제 3 – 이모티콘 할인행사
이 문제는 가능한 모든 경우의 수를 탐색하면 해결할 수 있는 문제입니다.
각 이모티콘은 10%, 20%, 30%, 40%의 4가지 할인율을 가질 수 있습니다.
만약 이모티콘이 m개가 있다면, 각 이모티콘에 4가지 중 하나의 할인율을 적용할 수 있으므로 이모티콘을 할인하는 모든 경우의 수는 4^m 가지가 될 것입니다.
그런데 이모티콘의 최대 개수는 7개로 매우 적으며, 경우의 수는 최대 4^7인 16,384가지밖에 되지 않기 때문에 제한 시간 안에 모든 경우의 수를 탐색할 수 있습니다.
각 이모티콘에 할인율을 적용한 다음에는 각 사용자들이 이모티콘 구매에 돈을 얼마를 쓰게 되는지를 구합니다. 이것은 사용자 수를 n, 이모티콘 수를 m이라 했을 때, 간단한 반복문과 조건문을 통해서 O(n × m)에 구할 수 있습니다.
각 사용자가 이모티콘 구매에 돈을 얼마를 쓰는지 구합니다. 이모티콘 구매 비용이 기준 비용보다 더 든다면, 구매 비용을 0으로 만들고 이모티콘 플러스 가입자 수에 1을 더해줍니다. 그렇지 않다면 이모티콘 판매액에 비용을 더해줍니다.
이모티콘에 할인율을 적용하는 모든 경우의 수에 대해서 이 과정을 반복한다면 시간복잡도 O(4^n × n × m)의 문제를 해결할 수 있습니다.
먼저, 루트 노드를 살펴보면 1~7번 중 한가운데인 4번인 것을 알 수 있습니다.
그리고 1~3번 노드들은 루트 노드의 왼쪽 서브트리를 구성하고 있고, 5~7번 노드들은 루트 노드의 오른쪽 서브트리를 구성하고 있습니다.
또, 1~3번 노드들로 이루어진 서브트리의 루트 노드는 가운데 번호인 2번 노드이고, 5~7번 노드들로 이루어진 서브트리의 루트 노드는 가운데 번호인 6번 노드입니다.
이와 같이 각 서브트리의 루트 노드는 항상 가운데에 위치하기 때문에 가운데 번호를 가진 노드라는 것을 알 수 있고, 루트 노드를 기준으로 왼쪽은 왼쪽 서브트리를 구성하고, 오른쪽은 오른쪽 서브트리를 구성한다는 것을 알 수 있습니다.
이것을 재귀적으로 활용하면 우리는 이진수가 주어졌을 때, 원래 주어졌던 포화 이진트리를 구성할 수 있습니다. 이진수의 0은 더미 노드로, 1은 일반 노드로 치환합니다. 이진수의 한가운데 있는 숫자는 루트 노드로, 루트 노드의 왼쪽 숫자들은 왼쪽 서브트리, 오른쪽 숫자들은 오른쪽 서브트리로 구성합니다. 왼쪽 서브트리, 오른쪽 서브트리 또한 크기가 1이 될 때까지 재귀적으로 서브트리를 구성하면 원래의 포화 이진트리를 구성할 수 있습니다.
하지만 주어지는 수는 이진수가 아닌 십진수입니다. 십진수를 이진수로 변환했을 때, 포화 이진트리로 만들기 위한 자릿수가 부족한 경우가 생길 수 있습니다. 이때는 포화 이진트리로 만들 수 있는 자릿수가 될 때까지 앞에 0을 붙여주면 됩니다.
위와 같은 방법으로 십진수를 이진수로 변환하고 이진수를 포화 이진트리로 표현할 수 있습니다. 이제 루트 노드가 더미 노드가 아니면서, 더미 노드를 제거했을 때 하나의 이진트리를 구성하는지 확인하면 문제를 해결할 수 있습니다.
문제 5 – 표 병합
많은 응시자들이 DSU(Disjoint Set Union, 서로소 집합) 자료구조를 활용해 이 문제를 풀었습니다. 하지만 테스트케이스의 사이즈가 크지 않기 때문에 DSU와 같은 특별한 자료구조 없이도 문제 풀이가 가능합니다. 여러 가지 풀이 중 비교적 구현이 간단한 풀이를 설명하겠습니다.
먼저 50 × 50개 셀의 병합 상태를 판단하기 위해 50 × 50 크기의 2차원 배열 merged를 사용합니다. (r1, c1), (r2, c2) 두 위치에 대해 merged[r1][c1], merged[r2][c2]의 값이 같다면 두 위치는 병합된 한 셀로 판단합니다. 초기에는 모든 셀이 병합이 되어 있지 않으므로, 1 ≤ i ≤ 50, 1 ≤ j ≤ 50인 모든 i, j에 대해 merged[i][j]의 값을 (i, j)로 초기화합니다.
또한 병합된 셀의 문자열 값을 저장하기 위해 50 × 50 크기의 2차원 배열 content를 사용하며, 초기에 모든 셀은 비어 있으므로 content의 각 원소는 “EMPTY”로 초기화합니다.
commands 배열에 담긴 순서대로 다섯 가지 명령어에 대해 다음과 같이 처리합니다.
- “UPDATE r c value”
merged[r][c]의 값 (x, y)를 찾아 content[x][y]의 값을 value로 변경합니다.
- “UPDATE value1 value2”
content의 원소 중 값이 value1인 원소를 모두 value2로 변경합니다.
- “MERGE r1 c1 r2 c2”
merged[r1][c1]의 값 (x1, y1)과 merged[r2][c2]의 값 (x2, y2)를 찾습니다. 그 후 merged의 원소 중 값이 (x2, y2)인 원소를 모두 (x1, y1)로 변경하고, 문제의 설명에 따라 content[x1][y1]의 값을 변경합니다.
- “UNMERGE r c”
merged[r][c]의 값 (x, y)와 content[x][y]의 값 tmp를 찾습니다. merged[i][j]의 값이 (x, y)인 모든 i, j에 대해 merged[i][j]의 값을 (i, j)로, content[i][j]의 값을 “EMPTY”로 변경합니다. 마지막으로 content[r][c]의 값을 tmp로 변경합니다.
- “PRINT r c”
merged[r][c]의 값 (x, y)를 찾아 content[x][y]의 값을 정답 배열에 추가합니다.
위와 같이 명령어를 처리하면 명령어 한 개당 50 × 50 = 2500번 정도의 연산이 필요하며, 명령어의 최대 개수가 1000개이므로 충분히 빠른 실행 시간 안에 문제를 해결할 수 있습니다.
문제 6 – 미로 탈출 명령어
이 문제는 수학, 그리디, DFS(Depth First Search, 깊이 우선 탐색), 다이나믹 프로그래밍 등 여러 풀이가 있습니다. 그중 많은 응시자들이 사용한 DFS 풀이를 설명하겠습니다.
직관적으로 생각할 수 있는 방법은 다음과 같습니다.
현재 위치를 기준으로 미로를 벗어나지 않으면서 상, 하, 좌, 우로 이동 횟수가 k가 될 때까지 재귀적으로 반복해서 이동합니다. 만약 k 번 이동했을 때 탈출 지점에 도달했다면, 해당 커맨드를 정답 후보에 넣고 모든 탐색을 마친 뒤 정답 후보에서 사전 순으로 가장 빠른 문자열을 고릅니다. 하지만, 이 방법은 시간복잡도가 O(4^k)가 되어 시간 초과가 발생합니다.
따라서 위 방법을 최적화해야 합니다.
문자열을 사전 순으로 가장 빠르게 정렬하려면, 가장 앞에 나오는 문자가 사전 순으로 가장 빠른 문자여야 합니다. 즉 이동을 시작할 때부터 가장 빠른 문자로 이동하는 것이 좋습니다.
또, 위치 (x, y)에서 k번 이동까지 남은 이동 횟수 remain이 정해지면, 해당 상태에서 탈출까지 최적의 경로는 유일합니다. (remain = k – 현재 이동 횟수)
아래 글부터 (x, y, remain)을 묶어 상태라고 부르겠습니다.
따라서, 명령어를 사전 순으로 정렬한 d, l, r, u 순서대로 위에서 설명한 재귀 탐색을 각 상태에 대해서 방문 여부를 체크하면서 수행하면 됩니다. 이때, 이미 방문한 상태 (x, y, remain)을 다시 방문했다면 이미 사전 순으로 가장 빠른 경로가 존재하기 때문에 추가적인 탐색을 하지 않아도 됩니다.
따라서 가장 먼저 탈출지점에 remain = 0인 상태로 탈출하는 명령어가 사전 순으로 가장 빠른 명령어가 됩니다.
가장 먼저 방문한 결과가 사전 순으로 가장 빠른 결과임을 다음 과정을 통해 증명할 수 있습니다.
임의의 상태 (x, y, remain)에서 d, l, r, u 순서대로 다음 상태 (x’, y’, remain – 1)로 이동했다고 가정해보겠습니다.
가장 먼저 d 방향으로 이동해 현재까지 이동한 명령어가 “…d”라면, “…l”, “…r”, “…u” 로 이동한 어떤 결과도 “…d” 보다 사전 순으로 빠르지 않습니다.
따라서 (x’, y’, remain – 1)에서 (x’‘, y’’, remain – 2)로 이동할 때에도 같은 규칙을 적용하면, 사전 순으로 가장 빠른 문자열부터 탐색을 한다는 것을 알 수 있습니다. 그러므로 이미 방문한 상태 (x, y, remain)을 다시 방문했다면 사전 순으로 더 빠른 경로가 존재함을 알 수 있습니다.
다른 방법
문자열이 사전 순이어야 한다는 조건과 이동 거리가 정해져 있다는 점에서 탐색을 쓰지 않는 방법도 있습니다. 우선 사전 순서 조건을 고려하면 최적의 해는 d 반복 -> l 반복 -> rl 반복 -> r 반복 -> u 반복의 형태를 가집니다. 반복수를 구하는 방법은 d -> ‘l 또는 r’ -> u 순으로 최단 거리로 이동한 경로에 남은 거리(k – 최단 경로 길이)가 존재한다면 d, l, rl, r, u를 채워 넣는 방법입니다. 남은 거리는 (d, u), (l, r)이 대칭이 된다는 점과 격자의 크기를 이용해 (d, u), (l, r)을 최대한 채우고, 그래도 남는다면 rl 반복으로 채우면 최적의 해가 나옵니다.
문제 7 – 1,2,3 떨어뜨리기
이 문제는 숫자 1, 2, 3중 하나씩을 직접 떨어뜨리는 완전 탐색으로 풀 경우 시간 초과가 발생하게 됩니다.
- target 값이 100인 리프 노드 하나에 숫자를 떨어뜨리는 경우의 수는 180,396,380,815,100,901,214,157,639 가지입니다.
- 이런 리프 노드가 최대 100개까지 존재할 수 있습니다.
따라서 이 문제를 풀기 위해서는 약간의 생각의 전환이 필요합니다.
일단 숫자를 하나씩 떨어뜨리되 그 떨어진 숫자가 어떤 숫자인지는 고려하지 않고 어떤 리프 노드에 쌓이는지만 고려해 봅시다.
지문의 예시로 나온 트리에서 숫자를 하나씩 떨어뜨렸을 때 각 노드에 숫자가 몇 개씩 쌓이는지를 확인해 보겠습니다.
| 떨어트린 숫자 개수 | 각 노드에 쌓인 숫자 개수 |
|---|---|
|
0 |
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
|
|
1 |
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
|
|
2 |
[0, 0, 0, 1, 0, 0, 0, 1, 0, 0] |
|
3 |
[0, 0, 0, 1, 0, 0, 1, 1, 0, 0]
|
|
4 |
[0, 0, 0, 1, 0, 0, 1, 1, 1, 0] |
|
5 |
[0, 0, 0, 2, 0, 0, 1, 1, 1, 0] |
|
6 |
[0, 0, 0, 2, 0, 0, 1, 1, 1, 1] |
|
7 |
[0, 0, 0, 2, 0, 0, 2, 1, 1, 1] |
7개까지 숫자를 떨어뜨렸을 때 각 노드에 [0, 0, 0, 2, 0, 0, 2, 1, 1, 1]개씩 숫자가 쌓이게 됩니다. 또한, target이 [0, 0, 0, 3, 0, 0, 5, 1, 2, 3]이므로 4번 노드에 숫자가 2개 쌓여있고 만들어야 하는 합은 3입니다. 1 이상 3 이하의 숫자 2개를 더해서 3이 되려면 (1,2) 혹은 (2,1)이어야 합니다.
우리가 떨어뜨릴 수 있는 숫자는 1,2,3밖에 없으므로 아래와 같은 공식으로 모든 노드가 target 값을 만들 수 있는지를 숫자를 떨어뜨릴 때마다 체크해야 합니다.
현재 노드가 보유하고 있는 숫자 개수 ≤ 노드의 target 값 ≤ 현재 노드가 보유하고 있는 숫자 개수 * 3
따라서, target 값대로 리프 노드에 숫자를 쌓을 수 있는지 확인하려면 다음과 같은 과정을 거쳐야 합니다.
- 트리에 숫자를 떨어뜨립니다.
- 각 리프 노드에 숫자가 몇 개씩 떨어졌는지 카운팅합니다.
- 현재까지 떨어뜨린 숫자의 개수로 모든 리프 노드에서 target 값을 만들 수 있는지를 위의 공식을 통해 확인합니다.
- 만약 모든 리프 노드의 target 값을 만들 수 있다면 루프를 탈출합니다. 이때가 가장 적은 숫자를 사용하여 target 값대로 리프 노드에 숫자를 쌓을 수 있는 때입니다. target 값을 만들 수 없는 리프 노드가 하나라도 있다면 (1.)로 돌아갑니다.
단, target을 만들 수 없는 트리가 입력으로 주어졌다면, 위 과정에서 무한 루프를 돌 수 있습니다. 어떤 노드에서 현재까지 떨어뜨린 숫자로 target 값을 만들 수 없는 경우는 다음과 같이 2가지가 있습니다. 이 중에서 2번째 경우가 target을 만드는 것이 불가능한 트리가 주어진 경우입니다.
- 노드의 target 값 > 현재 노드가 보유하고 있는 숫자 개수 * 3인 경우는 현재 보유하고 있는 숫자 개수가 적어서 target 값을 만들 수 없는 경우이므로 숫자를 더 떨어트리면 target 값을 만들 수 있습니다.
- 현재 노드가 보유하고 있는 숫자 개수 > 노드의 target 값인 경우는 현재 보유하고 있는 숫자를 모두 1로 바꿔도 target을 만들 수 없습니다. 따라서 영원히 target대로 숫자의 합을 만들 수 없으므로, 더 이상 루프를 돌지 말고 [-1]을 return 해야 합니다.
여기까지가 target대로 숫자의 합을 만들 수 있는지 없는지를 구하고, 만들 수 있는 경우 사용하는 숫자의 최소 개수까지 구하는 과정이었습니다.
이제 만들 수 있는 답 중 사전 순으로 가장 빠른 경우를 찾아보겠습니다.
일단 주어진 예시에서는 숫자 7개로 숫자의 합을 target과 같이 만들 수 있었으므로 answer 배열의 길이는 7이어야 합니다. (answer 배열: [?, ?, ?, ?, ?, ?, ?])
위 예시에서 각 노드에 쌓인 숫자 개수를 나타내는 배열 [0, 0, 0, 2, 0, 0, 2, 1, 1, 1] 대신
각 노드에 몇 번째로 떨어트린 숫자가 쌓였는지를 기록하면 [[], [], [], [1, 5], [], [], [3 ,7], [2], [4], [6]]이 됩니다. 이렇게 기록할 경우 각 배열의 길이로 노드에 쌓인 숫자의 개수를 구할 수 있으며 어떤 리프 노드에 몇 번째 숫자가 쌓였는지도 같이 확인할 수 있습니다. 4번 노드에는 1번째로 떨어뜨린 숫자와 5번째로 떨어뜨린 숫자가 쌓이고 7번 노드에는 3번째로 떨어트린 숫자와 7번째로 떨어뜨린 숫자가 쌓입니다.
4번 노드는 숫자 2개로 3을 만들어야 하므로 answer 배열의 1번째 원소에는 1이 5번째 원소에는 2가 들어가야 합니다. (answer 배열: [1, ?, ?, ?, 2, ?, ?])
마찬가지로 7번 노드는 숫자 2개로 5를 만들어야 하므로 answer 배열의 3번째 원소에는 2가 7번째 원소에는 3이 들어가야 합니다. (answer 배열: [1, ?, 2, ?, 2, ?, 3])
8, 9, 10번 노드의 경우는 숫자 하나로 target 값을 만들어야 하므로 target 값 그대로를 사용해야 합니다. (answer 배열: [1, 1, 2, 2, 2, 3, 3])
이렇게 그리디하게 answer 배열의 앞쪽에 오는 원소에는 최대한 작은 숫자를 넣으면 답을 구할 수 있습니다.
target대로 숫자의 합을 만들 수 있는지 O(n^2 * m) 만에 확인이 가능합니다.
그리디하게 answer 배열을 채우는 과정은 O(n * m) 만에 가능하므로 총 시간복잡도 O(n^2 * m) 만에 풀 수 있습니다.
마치며
지금까지 2023 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 문제와 풀이에 대해 살펴보았습니다.
설명드린 풀이 외에도 다양한 풀이법이 있습니다. 그래서 풀이를 암기하기보다는 어떠한 흐름으로 풀이가 진행되는지를 이해하고, 다른 방법으로 풀 수는 없는지에 대해 고민해 보면 큰 도움이 될 것입니다.
마지막으로 2023 KAKAO BLIND RECRUITMENT에 많은 관심 가져 주셔서 감사드리며, 5시간이라는 긴 시간 동안 테스트 응시하시느라 정말 고생 많으셨습니다!
