2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테스트가 지난 2021년 5월 8일에 4시간에 걸쳐 진행되었습니다.

이번 인턴 코딩 테스트에서는 5문제가 출제되었습니다. 이전과 동일하게 쉬운 문제를 앞쪽에, 어려운 문제를 뒤쪽에 배치하였으며, 일부 문제에는 효율성 테스트 케이스를 추가하여 효율적으로 문제를 해결한 참가자들이 더 많은 점수를 얻을 수 있도록 하였습니다. 이때 동점인 경우를 제외하면 모든 테스트 케이스를 맞혀야 해당 테스트 케이스 세트에 대한 점수를 얻을 수 있도록 하였으며, 정확성과 효율성 테스트 케이스는 점수를 별도로 부여하였습니다.

그럼 각 문제별 해설을 살펴보겠습니다.

문제 1

문제 풀이 : Lv1. 숫자 문자열과 영단어

1478 → “one4seveneight”
234567 → “23four5six7”
10203 → “1zerotwozero3”

네오와 프로도가 위와 같이 숫자를 문자열로 바꾸는 게임을 하고 있습니다. 이때 일부 자릿수가 영단어로 바뀌었거나 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어질 때, s가 의미하는 원래 숫자를 return 하는 함수를 완성해 주세요.

제한사항

1 ≤ s의 길이 ≤ 50
s가 “zero” 또는 "0"으로 시작하는 경우는 주어지지 않습니다.
return 값이 1 이상 2,000,000,000 이하의 정수가 되는 올바른 입력만 s로 주어집니다.

입출력 예

s	result
`"one4seveneight"`	1478
`"23four5six7"`	234567
`"2three45sixseven"`	234567
`"123"`	123

입출력 예 설명

- 입출력 예 #1, #2

문제 예시와 같습니다.

- 입출력 예 #3

"three"는 3, "six"는 6, "seven"은 7에 대응되기 때문에 정답은 입출력 예 #2와 같은 234567이 됩니다.
입출력 예 #2와 #3과 같이 같은 정답을 가리키는 문자열이 여러 가지가 나올 수 있습니다.

- 입출력 예 #4

s에는 영단어로 바뀐 부분이 없습니다.

제한시간 안내

정확성 테스트 : 10초

문제 해설

문제에 제시된 내용을 충실하게 구현하면 풀 수 있는 문제입니다. 여러 접근 방법이 있을 수 있는데, 대표적인 방법은 다음과 같습니다.

for 문 등의 반복문을 사용하여 한 글자씩 읽으면서 숫자인 경우 그대로 출력하고, 알파벳 문자인 경우 zero~nine 중 해당되는 것이 있으면 숫자로 바꾸고, 아니면 다음 문자를 계속 확인하는 방식
언어별 기본 라이브러리에 있는 문자열 replace 함수를 사용하는 방식

문제 2

문제 풀이 : Lv2. 거리 두기 확인하기

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야 하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리 두기를 위하여 응시자들 끼리는 맨해튼 거리가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

✔ 맨해튼 거리: 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2|입니다.

예를 들어,

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리 두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리 두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
places의 열 길이(대기실 세로 길이) = 5
places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
- places에 담겨 있는 5개 대기실의 순서대로, 거리 두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리 두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

places	result
`[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPXX", "OXXXP", "POOXX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]`	[1, 0, 1, 1, 1]

입출력 예 설명

- 입출력 예 #1

첫 번째 대기실


No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

모든 응시자가 거리 두기를 지키고 있습니다.

두 번째 대기실


No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

(0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리 두기를 지키고 있지 않습니다.
(1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리 두기를 지키고 있지 않습니다.
(4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리 두기를 지키고 있지 않습니다.

세 번째 대기실


No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	X	X
3	O	X	X	X	P
4	P	O	O	X	X

모든 응시자가 거리 두기를 지키고 있습니다.

네 번째 대기실


No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

대기실에 응시자가 없으므로 거리 두기를 지키고 있습니다.

다섯 번째 대기실


No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

모든 응시자가 거리 두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리 두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

제한시간 안내

정확성 테스트 : 10초

문제 해설

주어진 5x5 크기의 대기실을 다음과 같은 그래프로 볼 수 있습니다.

하나의 칸을 정점으로 봅니다.
모든 칸에는 상하좌우 인접한 칸으로의 간선이 있습니다.
단, 파티션이 있는 칸에서 나오거나 파티션이 있는 칸으로 들어가는 간선은 없습니다.

그러면 이 문제는 사람이 있는 정점에서 거리 2 이내에 다른 사람이 있는 정점이 있는지를 검사하는 그래프 탐색 문제로 볼 수 있습니다.

따라서 사람이 있는 정점들에서 시작하는 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 알고리즘을 사용하면 해결이 가능합니다. 이때, 거리 2 이내만 확인하면 된다는 점에 유의하여 구현해야 합니다.

이 방법 이외에도, 거리 2 이내까지만 확인하면 문제를 풀 수 있기 때문에 이중 반복문을 사용해서 직접 한 칸씩 확인하는 것도 충분히 가능한 방법입니다.

문제 3

문제 풀이 : Lv3. 표 편집

업무용 소프트웨어를 개발하는 니니즈웍스의 인턴인 앙몬드는 명령어 기반으로 표의 행을 선택, 추가, 삭제, 복구하는 프로그램을 작성하는 과제를 맡았습니다. 세부 요구 사항은 다음과 같습니다.

위 그림에서 파란색으로 칠해진 칸은 현재 선택된 행을 나타냅니다. 단, 한 번에 한 행만 선택할 수 있으며, 표의 범위(0행 ~ 마지막 행)를 벗어날 수 없습니다. 이때, 다음과 같은 명령어를 이용하여 표를 편집합니다.

"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

예를 들어 위 표에서 "D 2"를 수행할 경우 아래 그림의 왼쪽처럼 4행이 선택되며, "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "네오"가 적힌 행을 선택합니다(4행이 삭제되면서 아래 있던 행들이 하나씩 밀려 올라오고, 수정된 표에서 다시 4행을 선택하는 것과 동일합니다).

다음으로 "U 3"을 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다.

다음으로 "D 4"를 수행한 다음 "C"를 수행한 후의 표 상태는 아래 그림과 같습니다. 5행이 표의 마지막 행이므로, 이 경우 바로 위의 행을 선택하는 점에 주의합니다.

다음으로 "U 2"를 수행하면 현재 선택된 행은 2행이 됩니다.

위 상태에서 "Z"를 수행할 경우 가장 최근에 제거된 "라이언"이 적힌 행이 원래대로 복구됩니다.

다시 한번 "Z"를 수행하면 그다음으로 최근에 제거된 "콘"이 적힌 행이 원래대로 복구됩니다. 이때, 현재 선택된 행은 바뀌지 않는 점에 주의하세요.

이때, 최종 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 "O", 삭제된 행은 "X"로 표시하면 다음과 같습니다.

처음 표의 행 개수를 나타내는 정수 n, 처음에 선택된 행의 위치를 나타내는 정수 k, 수행한 명령어들이 담긴 문자열 배열 cmd가 매개변수로 주어질 때, 모든 명령어를 수행한 후 표의 상태와 처음 주어진 표의 상태를 비교하여 삭제되지 않은 행은 O, 삭제된 행은 X로 표시하여 문자열 형태로 return 하도록 solution 함수를 완성해 주세요.

제한사항

5 ≤ n ≤ 1,000,000
0 ≤ k < n
1 ≤ cmd의 원소 개수 ≤ 200,000
- cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나입니다.
- X는 1 이상 100,000 이하인 자연수로만 주어지며 0으로 시작하지 않습니다.
- cmd에 등장하는 모든 X들의 값을 합친 결과가 1,000,000 이하인 경우만 입력으로 주어집니다.
- 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않습니다.
- 본문에서 각 행이 제거되고 복구되는 과정을 보다 자연스럽게 보이기 위해 "이름" 열을 사용하으나, "이름"열의 내용이 실제 문제를 푸는 과정에 필요하지는 않습니다. "이름"열에는 서로 다른 이름들이 중복 없이 채워져 있다고 가정하고 문제를 해결해 주세요.
표의 범위를 벗어나는 이동은 입력으로 주어지지 않습니다.
정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 해주세요.

정확성 테스트 케이스 제한 사항

5 ≤ n ≤ 1,000

효율성 테스트 케이스 제한 사항

주어진 조건 외 추가 제한사항 없습니다.

입출력 예

n	k	cmd	result
8	2	`["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]`	`"OOOOXOOO"`
8	2	`["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]`	`"OOXOXOOO"`

입출력 예 설명

- 입출력 예 #1

문제의 예시와 같습니다.

- 입출력 예 #2

다음은 9번째 명령어까지 수행한 후의 표 상태이며, 이는 입출력 예 #1과 같습니다.

10번째 명령어 "U 1"을 수행하면 "어피치"가 적힌 2행이 선택되며, 마지막 명령어 "C"를 수행하면 선택된 행을 삭제하고, 바로 아래 행이었던 "제이지"가 적힌 행을 선택합니다.

따라서 처음 주어진 표의 상태와 최종 표의 상태를 비교하면 다음과 같습니다.

제한시간 안내

정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

문제 해설

다양한 풀이가 존재할 수 있는 문제로, 그중 대표적인 풀이들을 소개합니다.

정확성 테스트 케이스 해설

주어진 표의 각 행의 삭제 여부를 배열에 저장합니다. 이 배열의 이름을 arr이라 하겠습니다.

예를 들어, 입출력 예 #2의 최종 상태에서 삭제되지 않은 행을 1, 삭제된 행을 0으로 표현하면 다음과 같이 표현할 수 있습니다.

[1, 1, 0, 1, 0, 1, 1, 1]

또한 중간 처리 과정을 위해 현재 선택된 행의 번호도 저장해야 합니다. selected 변수에 저장했다고 하겠습니다.

이러한 자료구조를 사용해 문제에 주어진 명령을 구현하면 다음과 같습니다.

"U X": arr배열을 순회하면서 삭제되지 않은 행 X개 만큼 위쪽으로 selected값을 조절합니다.
- 예를 들면 arr = [1, 1, 0, 1, 0, 1, 1, 1]이고 selected = 3일 때 "U 2" 명령이 들어온 경우, 2번 행이 삭제된 상태이므로 selected = 0이 됩니다.
"D X": "U X"와 유사한 방식으로 처리할 수 있습니다.
"D X": selected의 값을 X만큼 증가시킵니다.
"C"
- 1. 선택된 행 삭제: arr[selected]를 0으로 변경하고, 나중에 "Z" 명령이 들어왔을 때를 대비하여 스택에 삭제된 행 번호를 저장합니다.
- 1. 선택된 행 변경: 삭제되지 않은 바로 아래 행으로 selected 값을 변경합니다. 이때, 삭제된 행이 마지막 행인 경우 삭제되지 않은 바로 위 행으로 변경합니다.
"Z": 스택에서 삭제되었던 행 번호를 가져와서 arr배열의 해당 행의 상태를 1로 변경합니다.

이렇게 구현할 경우, U, D, C 명령은 최악의 경우 O(n), Z 명령은 O(1) 에 처리할 수 있습니다.

정확성 테스트 케이스의 제한 조건에서 5 ≤ n ≤ 1,000이므로 충분히 해결할 수 있습니다.

효율성 테스트 케이스 해설

효율성 테스트 케이스의 경우, 5 ≤ n ≤ 1,000,000 이므로 배열을 사용해서 해결하기에는 수행시간이 너무 오래 걸립니다.

링크드 리스트 사용

단순히 특정 행의 상태만을 저장하는 것에서 벗어나 링크드 리스트의 아이디어를 사용합니다. 리스트의 각 노드는 삭제되지 않은 이전/이후 노드에 대한 정보를 가집니다.

예를 들어, 행이 4개가 있고, 1번과 2번 행을 차례로 삭제하는 경우 다음과 같이 표현할 수 있습니다.

이와 같은 방법으로 구현할 경우,

U, D: 선택된 노드에서 X 번만 링크를 따라가면 되기 때문에 O(X)에 처리할 수 있습니다.
C: 선택된 노드와 그 노드의 앞뒤로 연결된 노드들의 링크 정보만 변경해 주면 되기 때문에 O(1)에 처리할 수 있습니다.
Z: 삭제된 노드 정보를 스택에 담아 두면 나중에 해당 노드에 O(1)에 접근하여 링크 정보를 복구해 줄 수 있기 때문에 O(1)에 처리할 수 있습니다.

따라서, 문제에서 cmd에 등장하는 모든 X들의 합이 1,000,000 이하인 경우만 입력으로 주어진다고 하였으므로, 충분히 효율성 테스트 케이스를 통과할 수 있습니다.

Segment Tree 또는 Fenwick Tree 사용

실제 테스트에서 일부 참가자들이 사용한 풀이를 하나 소개합니다. 링크드 리스트 접근과는 완전히 다른 방식인데요, 먼저 정확성 풀이 처음에 나왔던 방식을 떠올려봅시다. 각 행의 삭제 여부를 0과 1로 나타냈던 방식입니다.

이때, 배열의 특정 구간의 합은 해당 구간의 삭제되지 않은 행의 수로 볼 수 있습니다.

그렇다면, U와 D 명령은 다음과 같이 생각할 수 있습니다.

U X: 현재 선택된 행에서, 그 위쪽 구간의 합이 X가 되는 지점으로 이동
D X: 현재 선택된 행에서, 그 아래쪽 구간의 합이 X가 되는 지점으로 이동

예를 들어, 하늘색 칸이 선택된 행을 나타낼 때, U 3 명령을 수행하려면 하늘색 칸 왼쪽으로 합이 3이 되는 지점까지 이동하면 됩니다. 즉, 노란색 부분의 합이 3이므로 그림에 표시된 지점까지 이동하는 것입니다.

이 방법을 사용하기 위해서는 선택된 행 위쪽 또는 아래쪽으로 얼마나 이동했을 때 구간 합이 X가 되는지를 빠르게 구해야 합니다. 만약 배열 전체를 순회할 경우 O(X)가 되어 배열을 사용한 풀이와 동일해지기 때문에 더 빠른 방법을 찾아야 합니다. 이를 위해 두 가지 기법을 사용합니다.

Segment Tree 또는 Fenwick Tree
- 이 자료구조를 이용하면 크기가 n인 배열의 구간 합을 O(log2 n) 시간에 구할 수 있습니다.
이분 탐색
- 선택된 행 앞, 또는 뒤로 몇 칸을 이동해야 할지를 이분 탐색을 사용해 O(log2 n)시간에 구할 수 있습니다.

두 기법을 조합하여 어느 지점까지 이동해야 할지를 O((log2 n)^2)시간에 구할 수 있습니다.

C, Z 명령의 경우는 정확성 테스트 케이스 풀이와 동일한 방법으로 처리할 수 있습니다.

이렇게 해결할 경우, 전체 cmd 수 ≤ 200,000 이고 5 ≤ n ≤ 1,000,000 이므로 효율성 테스트 케이스까지 해결할 수 있습니다.

문제 4

문제 풀이 : Lv4. 미로 탈출

신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다.

위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정에 걸리면 함정과 연결된 모든 화살표의 방향이 바뀝니다. 출발 지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.

그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다.
- 방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다.
- 화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
그림에 표시된 빨간색 방인 2번 방은 함정입니다.
- 함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어 있는 모든 길의 방향이 반대가 됩니다.
위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다.
- 똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다.
- 1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다.
- 함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다.
- 2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다.
- 탈출에 성공했습니다. 총 이동시간은 5입니다.

방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ n ≤ 1,000
1 ≤ start ≤ n
1 ≤ end ≤ n
1 ≤ roads의 행 길이 ≤ 3,000
roads의 행은 [P, Q, S]로 이루어져 있습니다.
- P에서 Q로 갈 수 있는 길이 있으며, 길을 따라 이동하는데 S만큼 시간이 걸립니다.
- 1 ≤ P ≤ n
- 1 ≤ Q ≤ n
- P ≠ Q
- 1 ≤ S ≤ 3,000
- 서로 다른 두 방 사이에 여러 개의 길이 존재할 수도 있습니다.
0 ≤ traps의 길이 ≤ 10
- 1 ≤ traps의 원소 ≤ n
- 시작 방과 도착 방은 함정이 아닙니다.
항상 미로를 탈출할 수 있는 경우만 주어집니다.

입출력 예

n	start	end	roads	traps	result
3	1	3	[[1, 2, 2], [3, 2, 3]]	[2]	5
4	1	4	[[1, 2, 1], [3, 2, 1], [2, 4, 1]]	[2, 3]	4

입출력 예 설명

- 입출력 예 #1

문제 예시와 같습니다.

- 입출력 예 #2

1 → 2 → 3 → 2 → 4 순서로 이동하면 됩니다. 총 이동시간은 4입니다.

제한시간 안내

정확성 테스트 : 10초

문제 해설

먼저, TRAP이 없다고 가정해 봅시다. 그러면 이 문제는 가중치가 양수인 간선만 있는 그래프에서의 두 노드 간의 최단거리를 찾는 문제로, 인접 리스트를 사용해 그래프를 구현한 후 다익스트라 알고리즘을 사용해서 해결할 수 있습니다.

TRAP이 있는 경우는 어떻게 해야 할까요? 문제의 조건에서, TRAP 노드의 최대 개수는 10입니다. 즉, TRAP 노드의 수가 적기 때문에 다익스트라 알고리즘을 사용하면서 그래프의 상태(즉, 어떤 노드에 연결된 간선들이 뒤집어져 있는지)까지 고려할 수 있습니다. 다익스트라 알고리즘에서 특정 노드를 방문하고, 다음 방문할 노드를 우선순위 큐에 넣는 과정에서 그래프의 상태를 확인하여 그 노드로 들어오는 간선과 노드에서 나가는 간선 중 사용 가능한 간선만을 골라서 사용하게 되는 것입니다. 일반적인 다익스트라 알고리즘 구현에서는 노드에서 나가는 간선만 고려하면 되지만, 이 문제에서는 들어오는 간선도 TRAP으로 인해 나가는 간선으로 바뀔 수 있기 때문에 모두 확인해 주어야 합니다. 또한, 원래의 다익스트라 알고리즘에서는 한 번 방문한 노드는 다시 방문할 필요가 없으나, 이 문제에서는 입출력 예 #2에서처럼 한 번 방문한 노드를 다시 방문해야 하는 경우도 있습니다. 이 경우는 방문할 때마다 그래프의 상태가 달랐기 때문으로, 다익스트라 알고리즘에서 "이미 방문한 정점"을 확인할 때 그래프의 상태가 달라진 경우에는 제외해서는 안 됩니다.

설명대로 구현한 경우, 그래프의 상태가 최대 2^10 = 1024 개 존재할 수 있으므로 간선과 정점의 수가 1024배로 늘어난 상태에서 다익스트라 알고리즘을 구현하는 것과 같으므로, 제한 시간 안에 문제를 해결할 수 있습니다.

문제 5

문제 풀이 : Lv5. 시험장 나누기

카카오 인턴을 선발하는 코딩 테스트 시험장이 하나의 이진 트리(모든 노드들의 자식 노드가 두 개 이하인 트리) 형태로 연결되어 있습니다. 아래 그림은 12개의 시험장이 연결된 예시입니다.

하나의 노드는 하나의 시험장을 나타냅니다.
노드 위의 검은 숫자는 해당 시험장의 고유 번호(ID)를 나타냅니다.
2-1. 시험장이 n개 있다면, 시험장의 고유 번호는 0부터 n-1까지 부여됩니다.
노드 안의 빨간 숫자는, 해당 시험장의 응시자 수를 나타냅니다.
3-1. 위의 그림에서, 9번 시험장에는 10명, 4번 시험장에는 8명, 6번 시험장에는 20명의 응시자가 시험을 볼 예정입니다.
노드 사이의 간선은 해당 시험장이 연결되어 있음을 의미합니다.
4-1. 위의 그림에서, 9번 시험장은 7번 시험장과, 7번 시험장은 6번 시험장과 연결되어 있습니다.

코딩 테스트를 총괄하는 무지는 안정적인 시험을 위해, 시험장에서 오는 트래픽을 k개의 그룹으로 나누어 각 그룹별 서버로 분산시키기로 하였습니다. 시험장 사이를 연결한 간선들 중 k-1개를 끊어서 시험장을 k 개의 그룹으로 나눌 계획입니다. 이때, 그룹별 최대 트래픽을 최소화하기 위하여 가장 큰 그룹의 인원을 최소화시켜야 합니다.

위의 그림에서 7번과 6번 시험장을 잇는 간선을 끊고, 9번과 7번 시험장을 잇는 간선을 끊는다면, 전체 시험장은 3개의 그룹으로 나누어집니다.

주황색 노드로 표시된 A그룹의 인원은 35명(10+8+5+6+1+1+4)
보라색 노드로 표시된 B그룹의 인원은 37명(7+30)
녹색 노드로 표시된 C그룹의 인원은 40명(20+8+12)

즉, 인원이 가장 많은 그룹은 40명입니다. 다른 어떤 방법으로 시험장을 3개의 그룹으로 나눈다고 해도, 인원이 가장 많은 그룹의 인원이 40명 미만이 되도록 나눌 수는 없습니다.

나눌 그룹의 수를 나타내는 정수 k, 각 시험장의 응시자 수를 나타내는 1차원 정수 배열 num, 시험장의 연결 상태를 나타내는 2차원 정수 배열 links가 매개변수로 주어집니다. 인원이 가장 많은 그룹의 인원이 최소화되도록 k개의 그룹으로 나누었을 때, 최소화된 최대 그룹의 인원을 return 하도록 solution 함수를 완성해 주세요.

제한사항

1 ≤ k ≤ 10,000
k ≤ num의 길이 ≤ 10,000
- num[i]에는 i번 시험장의 응시자 수가 담겨있습니다.
1 ≤ num의 원소 ≤ 10,000
links의 길이 = num의 길이
links의 i번째 행은 i번 노드(시험장)의 [왼쪽 자식 노드 번호, 오른쪽 자식 노드 번호]입니다.
- 해당 위치에 자식 노드가 없는 경우 -1이 담겨있습니다.
- 잘못된 노드 번호나, 하나의 이진 트리 구조가 아닌 입력은 주어지지 않습니다.

정확성 테스트 케이스 제한 사항

1 ≤ k ≤ 20
k ≤ num의 길이 ≤ 20

효율성 테스트 케이스 제한 사항

주어진 조건 외 추가 제한사항 없습니다.

입출력 예

k	num	links	result
3	[12, 30, 1, 8, 8, 6, 20, 7, 5, 10, 4, 1]	[[-1, -1], [-1, -1], [-1, -1], [-1, -1], [8, 5], [2, 10], [3, 0], [6, 1], [11, -1], [7, 4], [-1, -1], [-1, -1]]	40
1	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	27
2	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	14
4	[6, 9, 7, 5]	[[-1, -1], [-1, -1], [-1, 0], [2, 1]]	9

입출력 예 설명

- 입출력 예 #1

문제 예시와 같습니다.

- 입출력 예 #2

나눌 그룹의 수가 1개 이므로, 주어진 트리를 나눌 수 없습니다.
보라색 노드로 표시된 유일한 그룹의 인원은 27명입니다.

- 입출력 예 #3

나눌 그룹의 수가 2개이므로, 그림과 같이 1개의 간선을 끊어서 2개의 그룹으로 나눌 수 있습니다.
보라색 노드로 표시된 그룹은 13명, 주황색 노드로 표시된 그룹은 14명입니다.
따라서 최대 그룹의 인원은 14명입니다.

- 입출력 예 #4

나눌 그룹의 수가 4개 이므로, 그림과 같이 3개의 모든 간선을 끊어서 4개의 그룹으로 나눌 수 있습니다.
최대 그룹의 인원은 9명입니다.

제한시간 안내

정확성 테스트 : 10초
효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

문제 해설

정확성 테스트 케이스 해설

정확성 테스트 케이스에서는, links 의 길이 = num 의 길이 ≤ 20 이므로 20개의 간선 중에 일부를 끊어야 하는 상황입니다. 끊을 간선을 선택하는 가능한 최대 경우의 수는 20C10 = 184756 이므로 모든 경우를 시도해서 깊이 우선 탐색으로 가장 큰 그룹의 인원수를 구하는 완전 탐색 알고리즘으로 제한 시간 안에 문제를 해결할 수 있습니다.

효율성 테스트 케이스 해설

완전 탐색 알고리즘으로 문제를 해결하기에는 간선의 수가 너무 많기 때문에 다른 방법을 생각해야 합니다.

이 문제를 해결하기 위해서는 두 가지 아이디어를 조합해야 합니다.

파라메트릭 서치

파라메트릭 서치는 이분 탐색과 유사한 아이디어로, 이 문제와 같은 최적화 문제를 결정 문제로 바꾸어 푸는 데 사용됩니다.

주어진 최적화 문제: “트리를 k개 이하의 그룹으로 나누어서 얻을 수 있는 최소한의 최대 그룹의 크기는 얼마인가?”
변경된 결정 문제: “트리를 k개 이하의 그룹으로 나누어서 얻을 수 있는 최대 그룹의 크기가 L 이하가 되도록 할 수 있는가?”

위와 같이 문제를 변형하면, L의 최댓값을 이진 탐색을 통해 찾을 수 있습니다. 결정 문제의 답이 "Yes"인 최대의 L 값이 문제의 답이 됩니다.

트리를 k개 그룹으로 나누었을 때, 최대 그룹의 가중치 합이 (전체 가중치 합) / k보다 작을 수는 없기 때문에, 가능한 L 값의 범위는 다음과 같습니다.

(전체 가중치 합) / k ≤ L ≤ (전체 가중치 합)

이 범위에서 파라메트릭 서치를 진행해서 L 값을 찾아내면 됩니다.

다이나믹 프로그래밍

최대 그룹 인원이 L 이하가 되도록 트리를 자를 때, 필요한 그룹의 수가 k개 이하인지 판별하기 위해 다음과 같은 테이블을 정의합니다.

dp[i][0] = i번 노드를 루트 노드로 하는 서브트리를 최대 그룹 인원이 L 이하가 되도록 하기 위한 최소 그룹의 수

dp[i][1] = i번 노드를 루트 노드로 하는 서브트리를 최대 그룹 인원이 L 이하가 되도록 dp[i][0]개로 나누었을 때, i번 노드가 포함되는 서브트리의 가중치 합의 최솟값

예를 들어, 입출력 예 #1과 같이 트리가 구성되어 있고 L = 40일 경우,

dp[7][0] = 2, dp[7][1] = 37, dp[9][0] = 3, dp[9][1] = 35 입니다.

v번 노드에 대해, 다음 4가지 상황이 존재할 수 있습니다. v번 노드의 왼쪽 자식 노드를 i, 오른쪽 자식 노드를 j라고 하면,

(1) num[v] + dp[i][1] + dp[j][1] ≤ L 이면, v번 노드와 i번 노드, j번 노드가 속한 그룹을 모두 합해도 가중치 합이 L을 초과하지 않습니다. 즉 다음과 같이 할 수 있습니다.

dp[v][0] = dp[i][0] + dp[j][0] - 1
dp[v][1] = num[v] + dp[i][1] + dp[j][1]

(2) 조건 (1)에 해당하지 않고, (num[v] + dp[i][1] ≤ L) OR (num[v] + dp[j][1] ≤ L) 이면, 두 자식 노드가 속한 그룹들 중 하나의 그룹만 v번 노드와 합칠 수 있습니다. 이때 dp[v][1] 을 최소로 유지할 수 있는 자식 노드 그룹과 합칩니다.

dp[v][0] = dp[i][0] + dp[j][0]
dp[v][1] = num[v] + min(dp[i][1], dp[j][1])

(3) 조건 (1), (2)에 해당하지 않고, num[v] ≤ L 이면 양쪽 노드를 모두 잘라야 합니다.

dp[v][0] = dp[i][0] + dp[j][0] + 1
dp[v][1] = num[v]

(4) 조건 (1), (2), (3)에 모두 해당하지 않을 경우, v번 노드만 포함하는 그룹의 크기가 L보다 크므로 최대 그룹 인원이 L 이하가 되도록 트리를 k개 이하의 그룹으로 자를 수 없습니다.

위와 같은 방식으로 테이블을 모두 채웠을 때, 루트 노드 r 에 대해 dp[r][0] ≤ k인 경우 최대 그룹의 크기가 L 이하이도록 k개 이하의 그룹으로 나눌 수 있습니다. 이와 같은 방식으로 파라메트릭 서치를 통해 L의 최댓값을 찾을 수 있고, 그 값이 문제의 정답이 됩니다.

이렇게 문제를 해결할 경우, 파라메트릭 서치에 O(log2(sum(num))) 의 시간이 걸리고, L의 값을 정하는 데 필요한 테이블을 채우는 데에 O(len(num))의 시간이 걸립니다. 즉, 전체 시간 복잡도는 O(log2(sum(num)) * len(num))가 되어 빠르게 효율성 테스트 케이스를 통과할 수 있습니다.

마치며

지금까지 2021 카카오 인턴십 for Tech Developers 코딩 테스트 문제와 풀이를 살펴보았습니다.

본문에서 제시된 풀이는 여러 가지 가능한 풀이 중 일부로 여러 가지 접근이 있을 수 있습니다. 또 3번 문제의 Fenwick Tree 풀이처럼 일부 참가자들이 사용한 재미있는 접근도 담아 보고자 하였습니다. 참가자 여러분이 사용한 풀이법과 본문에서 소개한 풀이법 이외에도 또 다른 접근을 고민해 보시는 것도 많은 도움이 될 것이라 생각합니다.

이번 테스트에 응시해 주신 모든 분들께 감사드리며, 항상 건강에 유의하시고 카카오에서 뵙기를 기대하겠습니다.

감사합니다.

✔️ 카카오 온라인 코딩 테스트 문제해설 바로가기

2021 카카오 인턴십 for Tech developers 코딩 테스트 해설