“2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난 2019년 11월 9일 오후 2시부터 6시까지 총 4시간에 걸쳐 진행되었습니다.

'19년 신입공채 1차 코딩 테스트 시에 7문제가 출제되고 5시간의 풀이 시간이 주어졌던 것과는 달리 이번 인턴 코딩 테스트는 5문제가 출제되고 4시간의 풀이 시간이 주어졌습니다. 인턴의 경우 신입 공채와는 달리 인턴 과정을 통해 추가 검증을 하기 때문입니다.

이전과 동일하게 쉬운 문제를 앞쪽에, 어려운 문제를 뒤쪽에 배치하여 지원자가 처음부터 어려운 문제를 만나 당황하지 않도록 배치해 두었습니다. 그리고 테스트의 변별력을 높이기 위해 4번, 5번 문제의 경우 정확성 TC 외에 효율성 TC를 추가하여 문제를 제한된 시간과 주어진 환경에서 문제 없이 수행될 수 있도록 더 효율적인 방법으로 풀었을 때 효율성 TC를 통과하여 추가 점수를 획득할 수 있도록 하였습니다.

그럼, 이제 문제에 대한 풀이 방법을 살펴보도록 하겠습니다.

문제 1

문제1 풀러 가기

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

crane_game_101

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

board	moves	result
[[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]]	[1,5,3,5,1,2,1,4]	4

입출력 예에 대한 설명

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

문제 풀이

문제에 주어진 대로 구현하면 되는 문제입니다. 격자 칸에서 가장 위에 있는 인형을 찾기 위해 다음과 같은 방법을 사용할 수 있습니다.

인형을 집어 올릴 위치에서 0이 아닌 숫자가 나올 때까지 아래 방향으로 탐색합니다. 바닥에 도착하기 전에 인형을 발견하면 해당 위치를 0으로 만들고 바구니에 담습니다.

이때, 스택 또는 큐 등의 자료구조를 이용해서 가장 위에 있는 인형을 찾을 수도 있습니다. 예를 들어 5 x 5 크기 게임 화면의 경우 각 위치에 해당하는 스택 5개를 만들고, 가장 밑에 있는 인형부터 순서대로 넣어둡니다. 이제 가장 위에 있는 인형은 각 스택의 Top에 해당하며, 인형을 집어 올릴 때는 각 위치에 해당되는 스택에서 Pop 하면 됩니다.

집어 올린 인형을 바구니에 쌓을 때도 스택을 이용하면 됩니다. Top에 위치한 인형과 비교해서 서로 다른 인형이면 스택에 Push 하고, 같은 인형이라면 스택에서 Pop 하면서 터트려 사라지는 개수를 증가시킵니다.

문제 2

문제2 풀러 가기

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, …, an)

튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, …, an은 자연수), 이는 다음과 같이 집합 기호 ‘{’, '}'를 이용해 표현할 수 있습니다.

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, … {a1, a2, a3, a4, …, an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
{{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 5 이상 1,000,000 이하입니다.
s는 숫자와 ‘{’, ‘}’, ‘,’ 로만 이루어져 있습니다.
숫자가 0으로 시작하는 경우는 없습니다.
s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

입출력 예

s	result
`"{{2},{2,1},{2,1,3},{2,1,3,4}}"`	[2, 1, 3, 4]
`"{{1,2,3},{2,1},{1,2,4,3},{2}}"`	[2, 1, 3, 4]
`"{{20,111},{111}}"`	[111, 20]
`"{{123}}"`	[123]
`"{{4,2,3},{3},{2,3,4,1},{2,3}}"`	[3, 2, 4, 1]

입출력 예에 대한 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

문제 예시와 같습니다.

입출력 예 #3

(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

문제풀이

특정 튜플을 나타내는 집합이 주어질 때, 이를 이용해 원래 튜플을 구하는 문제입니다. 튜플로 변환해야 하는 집합이 문자열 형태로 주어지므로 먼저 각 집합에 속한 원소들을 분리합니다. ‘{’, ‘}’ 기호 안에 있는 숫자들을 ','를 기준으로 분리한 후, 각 원소를 배열에 넣습니다. 예를 들어 문제에 주어진 예시 5번의 경우 "{{4,2,3},{3},{2,3,4,1},{2,3}}"를 분리해 배열에 넣은 모습은 아래와 같습니다.

[4,2,3]
[3]
[2,3,4,1]
[2,3]

튜플의 첫 번째 원소까지 들어간 집합의 크기는 1, 두 번째 원소까지 들어간 집합의 크기는 2 … n 번째 원소까지 들어간 집합의 크기는 n이므로, 위에서 분리한 배열들을 길이 순서로 오름차순 정렬합니다.

[3]
[2, 3]
[4, 2, 3]
[2, 3, 4, 1]

이제, 집합의 길이가 1인 첫 번째 배열이 튜플의 첫 번째 원소를 나타낸다는 사실은 쉽게 알 수 있습니다. 또, 원소 수가 K인 집합과 K - 1인 집합의 차집합(단, K > 1)의 원소가 튜플의 K번째 원소를 나타낸다는 사실도 알 수 있습니다.

예를 들어 원소 수가 2인 집합 {2, 3}과 원소 수가 1인 집합 {3}의 차집합 {2, 3} - {3} = {2}이므로 구해야 하는 튜플의 두 번째 원소는 2가 됩니다. 마찬가지로 원소 수가 3, 4인 집합에 대해서도 차집합을 구해주면 구해야 하는 튜플은 (3,2,4,1)이 됩니다. 이때, 차집합은 길이가 K - 1인 배열에 없는 숫자를 길이가 K인 배열에서 찾는 방식으로 구현해주면 됩니다.

문제 3

문제3 풀러 가기

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 “프로도” 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 ‘*’ 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 ‘*’ 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 ‘*’ 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디
frodo
fradi
crodo
abc123
frodoc

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자
frd
abc1**

불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제재 아이디
frodo
abc123

제재 아이디
fradi
abc123

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

제한사항

user_id 배열의 크기는 1 이상 8 이하입니다.
user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
응모한 사용자 아이디들은 서로 중복되지 않습니다.
응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 ‘*’ 로만 이루어져 있습니다.
불량 사용자 아이디는 ‘*’ 문자를 하나 이상 포함하고 있습니다.
불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

입출력 예

user_id	banned_id	result
`["frodo", "fradi", "crodo", "abc123", "frodoc"]`	`["frd", "abc1**"]`	2
`["frodo", "fradi", "crodo", "abc123", "frodoc"]`	`["rodo", "rodo", "******"]`	2
`["frodo", "fradi", "crodo", "abc123", "frodoc"]`	`["frd", "rodo", "***", "****"]`	3

입출력 예에 대한 설명

입출력 예 #1

문제 설명과 같습니다.

입출력 예 #2

다음과 같이 두 가지 경우가 있습니다.

제재 아이디
frodo
crodo
abc123

제재 아이디
frodo
crodo
frodoc

입출력 예 #3

다음과 같이 세 가지 경우가 있습니다.

제재 아이디
frodo
crodo
abc123
frodoc

제재 아이디
fradi
crodo
abc123
frodoc

제재 아이디
fradi
frodo
abc123
frodoc

문제풀이

제한사항이 비교적 작으므로, 가능한 모든 방법을 시도해 보는 방식으로 문제를 해결할 수 있습니다. 응모자 아이디 목록의 길이가 N, 불량 사용자 아이디 목록의 길이가 K 일 때, 응모자 아이디 N개 중 K개를 선택하는 모든 방법을 시도해 봅니다. 선택된 아이디 목록이 불량 사용자 목록으로 매핑될 수 있다면 카운트를 하나 증가시킵니다. 최종적으로 매핑에 성공한 횟수를 반환하면 됩니다.

문제 4

문제4 풀러 가기

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항

k는 1 이상 1012 이하인 자연수입니다.
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

입출력 예

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다. 네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번…] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

문제 풀이

정확성 해설 : 정확성의 경우 길이가 k + 1인 배열을 잡은 후, 각 손님에 대해 차례대로 방을 배정하는 시뮬레이션을 진행하면 통과할 수 있습니다.

효율성 해설 : 다음과 같은 방법을 통해 효율성 풀이를 통과할 수 있습니다.

먼저 고객에게 배정할 방이 빈 방이면 즉시 배정합니다. 이때, 배정된 방 번호를 노드로 만들어 준 후, 부모 노드는 단순히 현재 방 번호에 1을 더한 값으로 지정합니다.

만약 고객에게 배정할 방이 빈 방이 아니면 다음과 같이 배정할 빈 방을 탐색합니다.

현재 노드의 방이 빈 방이 아니면 빈 방이 나올 때까지 부모 노드를 계속 방문합니다.
빈 방이 나오면 고객에게 배정하고, 배정된 방 번호를 노드로 만든 후, 부모 노드는 배정된 방 번호에 1을 더해준 값으로 지정합니다.
빈 방이 나오기 전까지 방문한 노드들의 부모 노드 또한 고객에게 배정한 방 번호에 1을 더한 값으로 수정합니다.

예를 들어 고객들이 원하는 방 번호가 순서대로 [1, 3, 1, 1]인 경우 다음과 같이 빈 방을 찾게 됩니다.

먼저 1번 방이 비어있으므로 즉시 배정 후, 부모 노드를 2번 방으로 지정합니다.

3번 방이 비어있으므로 즉시 배정 후, 부모 노드를 4번 방으로 지정합니다.

1번 방이 빈 방이 아니므로 부모 노드인 2번 방을 방문합니다. 2번 방은 빈 방이므로 즉시 방을 배정하고 바로 다음 방인 3번 방을 부모 노드로 지정합니다. 또, 이전에 방문한 1번 방의 부모 노드 또한 3번 방으로 지정해줍니다.

1번 방이 빈 방이 아니므로 부모 노드인 3번 방을 방문합니다. 3번 방 또한 빈 방이 아니므로 부모 노드인 4번 방을 방문합니다. 4번 방은 빈 방이므로 즉시 방을 배정하고 바로 다음 방인 5번 방을 부모 노드로 지정합니다. 또, 이전에 방문한 1번, 3번 방의 부모 노드 또한 5번 방으로 지정합니다.

만약 다른 고객이 다시 1번 방을 원할 경우, 중간 방들을 건너뛰고 5번 방부터 탐색한다는 사실을 위 그림을 통해 알 수 있습니다. 이와 같이 방문하는 방의 부모 노드를 갱신해 주면서 방을 배정해 나가면 고객에게 배정해야 되는 방의 번호를 빠르게 찾을 수 있습니다. 이때, 전체 방 개수가 10^12 개 이므로 배열을 이용해 모든 방을 나타낼 경우 메모리가 부족하게 됩니다. 고객들에게 배정되는 방 개수는 최대 20만 개 이므로, HashMap 등을 이용해서 필요한 만큼 노드를 생성하면 메모리를 절약할 수 있습니다.

문제 5

문제5 풀러 가기

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
stones 배열의 크기는 1 이상 200,000 이하입니다.
stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
k는 1 이상 stones의 길이 이하인 자연수입니다.

입출력 예에 대한 설명

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

문제 풀이

정확성 해설 : 친구들이 더 이상 징검다리를 건널 수 없을 때까지 시뮬레이션해본 후, 최대 몇 명이 건널 수 있는지 구해주면 됩니다.

효율성 해설 : 다양한 풀이가 있을 수 있으며, 다음과 같은 방법을 통해 효율성 풀이를 통과할 수 있습니다.

연속된 K개의 디딤돌에 적힌 숫자가 모두 0인 구간이 있으면 더 이상 징검다리를 건널 수 없으며, 이를 이용해 이분 탐색하면 문제를 해결할 수 있습니다. 먼저 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 M - 1 번째 친구까지 징검다리를 건넌 상황을 구합니다. 이때, M - 1번째 친구까지는 K값에 관계없이 모두 징검다리를 건넜다고 가정합니다. 따라서, 징검다리에 적힌 숫자가 M보다 작다면 숫자가 0이 됐다고 표시해주면 됩니다. 이제 M번째 친구가 징검다리를 건널 수 있는지 확인하기 위해 징검다리에서 0이 연속으로 K개가 나오는 구간이 있는지 확인합니다.

0이 연속으로 K개가 나오는 구간이 있는 경우 : M번째 친구는 징검다리를 건널 수 없습니다.
또한, M번째 친구보다 뒤에 건너는 친구들은 모두 징검다리를 건널 수 없습니다.
따라서 찾아야 하는 답은 0 이상 M - 1 이하인 정수 중 하나입니다.
0이 연속으로 K개가 나오는 구간이 없는 경우 : M번째 친구는 징검다리를 건널 수 있습니다.
이 경우 첫 번째 ~ M - 1 번째 친구들은 모두 정상적으로 징검다리를 건널 수 있습니다.
따라서 찾아야 하는 답은 M 이상 MAX값 이하인 정수 중 하나입니다.

답이 될 수 있는 최솟값과 최댓값의 중간값으로 M값을 계속 변경해 주면 효율적으로 탐색 범위를 줄여나갈 수 있습니다. 위 풀이의 경우 시간 복잡도는 O(nlogm)이 되며, n은 디딤돌의 개수, m은 디딤돌에 적힌 숫자의 최댓값입니다. 이 외에 O(n) 풀이 방법도 있으니 한 번 고민해보세요.

마치며

지금까지 카카오의 2019 겨울 개발자 인턴십 온라인 코딩테스트 문제와 풀이를 설명 드렸습니다. 문제마다 직접 풀어볼 수 있는 링크가 제공되니 테스트에 응시하지 않으셨던 분도 풀어보시면 좋을 것 같아요. 테스트에 응시하셨던 분들은 본인의 풀이법과 해설의 차이를 비교해 보시는 것도 흥미로울 겁니다.

카카오 입사를 염두에 두고 계시다면, 이번 문제풀이를 포함하여 테크블로그에 공개되어 있는 카카오의 온라인 코딩 테스트 기출문제를 풀어보시는 것을 추천합니다. 기출 문제를 통해 카카오가 원하는 논리적인 사고방식을 필요로 하는 문제들을 충분히 학습하시고 참여하신다면, 향후 좋은 결과를 얻을 수 있지 않을까 합니다.

계속되는 코로나19 확산으로 진행유무에 대한 변수가 있을 수는 있지만, 올 여름에도 2020 개발자 인턴십을 준비하고 있고, 계획대로 진행될 경우 4월 중순 경 접수 시작을 예상하고 있으니 카카오 영입 페이지에 지속적인 관심 가져주세요!

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

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설