[Algorithm] - 2020 Kakao InternShip for Tech Developers Coding test 문제 풀이

최근 들어 개인 프로젝트, 각종 테스트 등으로 인하여 블로그에 대한 글 포스팅이 자주 안되고 있는 점에 대해 깊이 반성하고 있습니다.

 

그런 계기로 하여금 오늘은 제가 내일 치루게 될 코딩테스트를 위해 오늘 하루 날을 잡고, 연습하게 되었는데요. 이번 포스트는 카카오 코딩테스트 문제 두 번째인 2020 카카오 인턴십 코딩테스트 문제 풀이와 짤막한 후기를 남겨보고자 합니다.

 

(참고로 이번 코딩 테스트는 난이도가 꽤 어려웠습니다.)

 

 

 

Question 01. 키패드 누르기

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

 

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

 

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 하는 알고리즘을 작성하는 문제입니다.

 

 

Solution for Question 01

처음 이 문제를 풀었을 때, 과거 첫 카카오 코딩테스트가 있었던 좌표 문제가 생각났습니다. 좌표를 이용하여 풀 되, 약간 꼬은 문제였으며 왼쪽 손가락의 전용 구간과 오른쪽 손가락의 전용 구간을 구분하고, 가운데 부분은 좌표 계산을 이용하면 쉽게 구할 수 있습니다.

 

이 문제를 가장 깔끔하게 처리할 수 있는 방법은 좌표를 클래스화하여 구현하는 것입니다. 빠르게 구현하고자 한다면 2차원 배열로 무작정 짜는 방법도 있겠지만 좌표의 클래스를 미리 구현하여 놓는다면 좀 더 가독성이 좋은 코드를 짤 수 있죠.

 

그 외에는 좌표 평면의 거리 공식을 이용하여 가까운 쪽에 해당하는 부분을 놓습니다. 만약 거리가 같다면 해당 문제에서 주어지는 손잡이를 이용하면 됩니다.

 

 

 

 

Question 02. 수식 최대화

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

 

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 특별한 방식으로 결정하려고 하며, 그 방식에 맞게 알고리즘을 구현하면 되는 문제입니다.

 

 

Solution for Question 02

이 문제는 재귀 함수를 이용하여 먼저 모든 조합을 찾아야 합니다. 무슨 조합을 찾냐구요? 바로 연산자의 조합인데요. 이를 찾아서 우선 순위가 먼저인 것, 나중인 것을 찾아 서로 합을 비교하고 가장 큰 값을 구하면 쉽게 풀 수 있는 문제입니다.

 

재귀 알고리즘을 통해 경우의 수를 구한다면 나머지는 쉽게 구현할 수 있습니다. HashSet을 그대로 사용해서 각 우선순위에 맞는 합계를 구현할 수도 있지만 좀 더 쉽게 Java 8의 스트림을 사용해서 List로 변환해준 것은 비밀...

 

 

 

Question 03. 보석 쇼핑

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

 

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 어떤 목적을 달성하고 싶었고, 그 목적은 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하는 것이며 모든 보석을 가장 짧은 구간으로 구매할 수 있는 범위를 찾는 알고리즘을 구현하는 문제였습니다.

 

 

Solution for Question 03

실제 테스트 당시 이 문제를 정말 어렵게 느꼈는데, 풀이를 보고나서 허탈한 느낌을 많이 받은 문제였습니다. 조건문 함정이 걸려 있어서, 조건문을 잘못 작성하면 쉽게 풀어지지 않는 문제였습니다. 공식 해설을 참고하여 해설대로 문제를 풀이하니, 잘 풀린다는... ㅠㅠ

 

이 문제의 핵심은 포인터를 이용하는 것입니다. 포인터를 이용해서 좌와 우를 조정하도록 하고, Map을 이용해서 보석의 종류를 모두 성립시켰는지 확인한 다음, 왼쪽 포인터를 차례로 이동시키고, 그렇지 않다면 우로 이동시키는데, 여기서 포인트는 보석의 종류가 모두 있는 상태인지를 검사를 먼저 진행하고, 그 다음 오른쪽 포인터의 끝마침 여부를 확인해야 한다는 점입니다. 만약 오른쪽 포인터의 마침점부터 먼저 확인한다면, 이 문제를 완벽하게 풀 수가 없습니다.

 

 

 

 

Question 04 경주로 건설

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

 

건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았고, 해당 경주로는 1 x 1 크기 형태의 격자로 구성되었으며 경주로를 건설하는 데 최소 비용을 구하는 알고리즘을 구현하는 문제입니다. 조건이 조금 까다로웠는데, 이 문제부터 어려워지기 시작합니다.

 

(자세한 문제는 원문을 참고해주세요.)

 

 

Solution for Question 04

이 문제는 너비 우선 탐색(BFS)을 이용해서 풀 수 있는 방법이 있습니다. 그러나 익숙하지 않은 알고리즘이라면 꽤 이해하기 어려운 문제였으며 구현도 쉽지 않을 것입니다. 

 

너비 우선 탐색에 대해 간단히 설명드리자면, 프로그래밍 방식으로 봤을 때, Queue를 이용해서 모든 경우를 돌고, 새로운 케이스가 만들어지면 큐에 계속 추가하여 끝내 큐에 있는 모든 대기열이 끝날 때까지 진행하는 방식입니다. 이 알고리즘 중간에 원하는 구현체를 만들면 쉽게 이 문제를 풀 수 있습니다.

 

클래스를 구성할 때 필요한 정보를 가능한 활용하는 것도 알고리즘 구현의 포인트입니다. 특히 Java 언어를 사용한다면 말이죠. 그리고 너비 우선 탐색은 방문했던 정보를 남기는 변수를 같이 사용하면 중복해서 방문하는 횟수를 줄이면서 알고리즘의 시간 복잡도를 줄일 수 있습니다.

 

이러한 방법을 이용하여 동, 서, 남, 북 모두를 순회하는데, 이 때 1 x 1 격자임을 감안함과 동시에 문제 조건인 벽인 경우를 감안하여 이동 위치가 벽이거나, 격자를 넘을 경우를 판단하는 메소드를 구현해야 합니다. 그런 다음 마지막으로 움직였던 방향과 비용을 사용하여 비용을 산정하고, 최소 비용을 구하면 됩니다.

 

 

 

Question 05. 동굴 탐험

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

 

오지 탐험가인 프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다. 

탐험에 앞서 프로도는 모든 방을 적어도 한 번 방문할 계획을 세웠고, 동굴 내 방에는 순회하기 위해 반드시 거쳐야하는 동굴이 있는데, 이들을 모두 포함하여 계획대로 수행할 수 있는지를 판단하는 알고리즘을 구현하면 되는 문제입니다.

 

 

Solution for Question 05

개인적으로 이번 문제 중에서 가장 어려웠던 최고 난이도 문제였습니다..

 

예시를 보면 가장 먼저 떠오르는 것은 그래프였기 때문에 당당하게 DFS로 문제 풀이를 시도 했지만 결과는 좋지 않았습니다. 제한 길이가 200,000이었고, 이 때문에 시간 초과가 난 것... ㅠㅠ

 

어떻게 풀지를 고민하다가 공식 해설을 보고 BFS로 푸는 것이 정답이라고 판단하였습니다. 4번 문제와 동일하게 Queue를 사용하여 방문 변수를 만들고 시도하였는데, 이 때 포인트를 잡은 것은 각 노드가 사이클하는지의 여부를 판단하는 것이었습니다. 이 여부를 잡을 수 있다면 해당 동굴을 모두 탐색할 수 있는지 없는지를 잡을 수 있었습니다. (정말 어려웠습니다 이 부분...)

 

 

 

마치며...

여기까지 카카오 코딩 테스트로 연습을 조금 해봤는데요. 이 연습을 하게 된 계기는 최근 해설이 올라왔다는 이야기를 듣게 되었고, 조만간 할 생각이었는데, 생각치 못한 프로그래밍 테스트로 인하여 솔루션 구현에 매진하다보니 코딩 테스트를 푸는 데 시간이 조금 걸리게 되었습니다.

 

개인적으로 이번 문제는 정말 난이도가 수준급 이상이었으며 특히 4번과 5번 문제는 Computer Science에서 수강하는 알고리즘 과목을 제대로 이수하지 않았거나 잘 이해하지 못하면 풀기 어려웠던 문제였습니다.

 

 

(이렇게 말해놓고 3번 문제도 제대로 못 푼 건 비밀....)

 

 

여기까지 2020 카카오 코딩 테스트 인턴 풀이였습니다.

 

 

 

참고: https://tech.kakao.com/2020/07/01/2020-internship-test/