[Algorithm] - 2019 Kakao Winter internship Coding test 문제 풀이

2년 전부터 계속, 시간이 날 때마다(그 시간이 얼마 되지 않지만..) 틈틈이 알고리즘 문제 풀이를 계속 이어가고 있었습니다.  다양한 문제들을 보았고, 어려운 문제, 생각이 날 것 같으면서도 뇌정지가 오는 문제, 쉽게 풀만한 문제들 다양한 문제들이 존재하였습니다.

그러던 중, 작년 겨울에 재미삼아 카카오 코딩 테스트 문제를 풀게 되었습니다. 문제 난이도는 생각한 것보다는 조금 어려운 수준에 해당했으며 어차피 코딩 테스트에서 좋은 성적을 거두지 못했더라도 차후에 문제 풀이 해설이 올라오기 때문에 가벼운 마음으로 시험에 임했습니다. 

하지만 몇 달이 지나도 해당 코딩테스트에 대한 문제 풀이 해설은 보이지 않았고, 그 해설을 최근에서야 발견하게 되었습니다.
(그것도 Google 검색이 친절하게 이것이 있다는 걸 알려줬다는...) 

그래서 이번 포스트에서는 2019년 겨울 카카오 인턴십 코딩 테스트에 대한 문제와 풀이, 그리고 짤막한 후기에 대해 간단하게 적어보고자 합니다.

 

 

Question 01. 크레인 인형 뽑기 게임

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/64061)

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. 죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 하는데, 게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이고, 위쪽에는 크레인, 오른쪽에는 바구니가 있으며 인형 한 개당 1 x 1 크기의 격자 한 칸을 차지하고, 가장 아래 칸부터 차곡차곡 쌓여있다고 합니다.

크레인 작동시, 인형을 놓치는 경우는 없고, 문제는 2차원 배열 board와 인형을 잡기 위해 크레인을 작동시킨 위치 좌표를 배열 moves에 매개 변수로 주어질 때, 크레인을 모두 작동시킨 후, 터뜨려서 사라진 인형의 갯수를 return하는 알고리즘을 구현하는 문제입니다.

(글 분량을 위해서 자세한 제한 사항과 문제에 대한 제약 사항에 대해서는 생략하도록 하겠습니다.)

 

Solution for Question 01

이 문제는 애니팡 게임과 비슷한 유형의 문제입니다. 애니팡의 경우 가로, 세로, 같은 캐릭터의 3개를 터뜨리는 것이지만, 이 게임은 1 x 1 크기의 배열에서 같은 캐릭터를 두 개 만나면 터뜨리는 갯수를 구하기만 하면 되는 문제입니다.

위 이미지에서 조금 힌트를 얻을 수 있습니다. 크레인 바로 밑에 그려진 5 x 5 크기의 격자는 boards라는 매개 변수에서 주어지기 때문에 우리는 이를 신경쓰지 않아도 됩니다. 옆에 있는 움직여서 사라지는 카카오 캐릭터들을 잘보면, Stack이라는 자료구조와 움직이는 모습이 매우 흡사합니다. 나중에 쌓인 애들이 순서대로 없어지는 Last in First Out (LIFO) 형태이지요.

따라서 아래와 같은 형태로 코드를 구현할 수 있습니다.

먼저 좌표를 보기 전에, 인형 보드를 탐색하는 것부터 시작하여 입력된 좌표를 보고, 하나씩 인형을 넣어주는 방식으로 알고리즘을 구현하면 됩니다. 그리고, 인형을 넣고 나서, 넣어진 인형을 검사하여 같은 인형이면 그의 갯수를 추가해서 넣어주면 쉽게 구할 수 있습니다.

 

 

Question 02. 튜플

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/64065)

셀 수 있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 이 튜플을 이용해 원소의 개수가 n개이고, 중복된 원소가 없는 튜플이 주어질 때, 매개변수의 튜플을 배열에 담아 반환하도록 하는 알고리즘을 구현하는 문제입니다.

 

Solution for Question 02

처음 이 문제를 풀었을 때 개인적으로 이해가 좀 많이 힘들었습니다. 튜플이라는 것은 셀 수 있는 수량의 순서 있는 열거 또는 어떤 순서라는 데, 사실 여기서부터 뇌정지가 왔습니다..

순서라고 한다면, 순서대로 배치하는 것만을 생각했기 때문이 잘못이라고 생각하였고, 튜플이라는 것을 문제에서 예시로 주어지는 것을 봤을 때, 앞의 숫자가 주어지면 그 뒤의 숫자가 하나씩 생기는 것으로 봐서는 뒤의 배열 형태의 원소를 하나씩 빼는 형태라고 보면 쉽게 생각할 수 있었는데, 이 부분을 해설이 나오고 난 뒤에 알게 되어서 조금 아쉬움이 많이 남는 문제였습니다.

그리고, 이 문제의 특징은 매개 변수가 Array(배열) 형태가 아닌 String(문자열) 형태로 주어지기 때문에 먼저 이 문자열 형태로 되어 있는 매개 변수를 각각의 원소로 분리하여 배열로 만들어야 합니다.

각각의 집합들이 괄호로 구분되어 있고, 그 원소들은 쉼표로 구분되어 있기 때문에 Java에서는 String 클래스에서 제공하는 split 메소드를 이용하면 쉽게 구분지을 수 있습니다. 

그리고, 각 숫자들은 String의 문자열 형태인데, 이를 정수 형태로 바꿔줘야 합니다. 복잡하게 한다면, 각 반복문을 돌아서 직접 자료형을 바꾸는 방법도 있겠지만 기왕 Java 8을 사용할 것이라면 Stream을 사용한다면 더 간결한 코드로 작성할 수 있겠죠.

마지막으로 해설에 나와있는대로 문제 풀이를 진행하기 위해 리스트를 튜플의 갯수에 맞춰 정렬을 해주도록 하면 전처리는 모두 끝입니다.

리스트를 정렬해준 이유는 Solution 메소드를 좀 더 쉽게 구현하는 데도 한 몫합니다. 예시를 보면, 집합의 길이가 1인 첫 번째 배열이 튜플의 1번째 원소를 가리키기 때문입니다. 앞쪽에서부터 작은 수를 주고, 뒤에서 두 집합의 차집합을 구해주면서, 원소들을 하나씩 추가해주는 방식으로 구한다면 원하는 튜플 형태가 나오게 됩니다.

그런데, 테스트에서는 Integer List가 아닌 int array로 반환하는 것을 요구하기 때문에 이 또한 Java 8의 Stream을 사용한다면 쉽게 변환할 수 있습니다.

 

 

Question 03. 불량 사용자

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/64064)

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

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

 

Solution for Question 03

이 문제 또한 몇 가지 함정이 많이 있습니다. 같은 패턴이 주어질 수도 있는데, 여기서 중요한 것은 중복되어 있는 패턴에 따라 중복된 아이디가 주어지면 안 된다는 것입니다.

그나마 불행 중 다행인 것은 배열의 크기가 1 ~ 8로 제한되어 있어, 완전 탐색 알고리즘으로 짜도 제약을 받지 않는다는 것입니다. 따라서 모든 경우를 전부 탐색하는 알고리즘으로 간다면 쉽게 풀 수 있는 문제였습니다.

Java에서는 matches와 replace 메소드를 이용해 정규식으로 원하는 패턴에 매칭되는 문자열을 찾을 수 있는 방법이 있습니다. 이 방법을 응용하면서 재귀 알고리즘을 구현할 수 있습니다.

그런데, 저는 여기에 비트 연산을 더하였습니다. 그 이유는 각각의 아이디가 중복이 될 수는 없어도, 패턴은 중복이 되어, 두 아이디가 들어갈 수도 있기 때문이었습니다. 각 Index에 2의 배수꼴로 취해지는 비트 연산을 통하여 각각의 ID를 더한다면 서로가 다른 집합으로 분류 계산된 결과가 나올 수 있습니다.

 

 

Question 04. 호텔 방 배정

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/64063)

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

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

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

 

Solution for Question 04

4번 문제부터는 효율성 테스트를 겸하는 문제가 나오게 됩니다. 이 때부터 쉽게 알고리즘을 구현해서 제출하면 낭패를 보게 되지요. 그래서 처음에 제출했을 땐 아래의 코드로 구현해서 제출하였습니다.

방 리스트를 Map으로 만들고, 해당 방이 예약되어 있는지를 Bool 값을 통해서 확인하는 형식으로 만들어서, 배정된 방일 경우에는 Java 8의 Stream을 사용하여 후보 방 리스트 중 가장 작은 방을 결정하는 식으로 한다면 쉽게 구할 수 있을 거라고 생각했습니다.

하지만 역시 효율성 테스트 전부 통과를 하지 못하였고, 여러 방면으로 고민한 끝에 Map이 역시 메모리를 많이 먹는다고 생각하여 두 번째 방법으로 배열을 사용하여 구분하면 조금 나아질 것이다는 생각을 하였지만 이 역시, 효율성 테스트 1~2개만 통과하고, 쉽사리 통과되지 않았습니다.

마지막으로 해설을 보게 되었고, 해설에서는 남아있는 방을 전부 탐색할 것이 아니라, 예약된 방을 제외한 나머지 방을 각 방 번호에 남겨주고, 그 방부터 탐색하게 하는 방법을 권하였습니다.

방을 전부 탐색하게 되면, 고객이 원하는 방 뿐만 아니라, 이미 예약된 방을 전부를 다시 조회하게 되는 불상사가 일어나는 것을 생각하여야 한다는 깊은 교훈을 깨닫게 해준 문제였습니다. 

 

 

Question 05. 징검다리 건너기

문제 원문: (https://programmers.co.kr/learn/courses/30/lessons/64062)

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

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

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

 

Solution for Question 05

5번 문제 역시, 효율성 테스트를 같이 보기 때문에 일반적인 방법으로 문제를 접근하기엔 풀기 어려운 문제였습니다.

가장 쉬운 방법은 k를 Life로 놓고, 그들의 값 중 0을 만나게 되면, Life를 감소하는 형식으로 접근하는 방법입니다. 그러고 모든 돌을 통과했다면, 승리 수를 올리면 건너는 사람의 총 합이 나오게 되겠죠.

그러나 이 방법은 O(n^2)의 시간복잡도를 가지기 떄문에 200,000개 배열 데이터를 처리하기에는 역부족이었습니다 ㅠㅠ.

그렇다면 어차피 k의 갯수만큼 0이 되어, 못건너가게 될 경우가 가장 먼저 패배될 가능성이 크므로, 모든 경우의 수를 전부 탐색하지 말고, k의 구간만큼 계산하여 그들 중 가장 작은 돌의 숫자를 구하면 최소한의 넘어갈 수 있는 사람이 나올 것입니다.

 

마치며...

카카오의 코딩 테스트는 언제든 풀어봐도 신선함과 아쉬움이 많이 남는 문제라고 생각합니다. 여러 유형의 문제들이 나와 쉬운 유형을 풀면, 뿌듯함이 느껴지는 반면, 효율성 테스트에서는 최적화에 대한 생각을 많이 하지 못해 아쉬움이 남고, 아예 정확도 테스트 조차도 못 푼 문제는 차후 해설을 보면, 이런 문제였구나 라는 것을 알 수도 있기 때문입니다.

출처: https://tech.kakao.com/2020/04/01/2019-internship-test/