[Algorithm] - 2022 카카오 신입 1차 온라인 코딩 테스트 (Kakao Newbie Primary Online Coding Test) for Tech developers 문제 풀이

매년 이뤄지는 카카오 신입 온라인 코딩 테스트 문제 풀이를 또 적게 되었네요. 회사 업무를 좀 더 신경써야 하다보니 마냥 푸는 것을 미뤄놓고만 있다 이제서야 문제 풀이를 진행하게 되었습니다.

 

이번에도 먼저 문제 풀이 전 후기를 잠깐 말씀드리자면 작년 문제에 비하여 난이도가 많이 개선된 모습이었습니다. 작년과 달리 Lv 4 문제는 출제 되지 않았고, 구현 중심의 앞 문제와 좀 더 실력을 보기 위한 Lv 3 난이도 문제 1~2문제로 추려진 모습이었습니다.

 

그럼 문제 풀이를 진행해보겠습니다.

 

 

 

Question 01. 신고 결과 받기

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

 

신입사원 무지는 게시판의 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려고 합니다. 특정 조건에 해당하는 게시판 불량 이용자를 찾아 누적 신고 횟수가 임계치를 넘은 이용자를 추려내는 프로그램을 작성하는 문제입니다.

(이전 글과 마찬가지로 문제에 대한 상세 사항은 생략합니다. 자세한 문제는 문제 원문을 참고해주세요.)

 

 

Solution for Question 01

1번 문제는 주어진 조건을 잘 이해하고 코드로 구현할 수 있는지 보는 기초적인 문제입니다. 작년과 같이 1번 문제는 주어진 요구사항을 잘 이해하고 내가 자신 있는 프로그래밍 언어로 잘 구현하는지를 보는 문제 같았습니다. 정답률이 무려 80%가 넘는군요.

 

Map과 Stream을 이용해서 풀면 filter를 이용해 특정 임계값을 넘는 구간만을 리스트로 재가공해서 보여줄 수 있습니다. 이 외에도 직접 for Loop을 사용할 수도 있을 것입니다.

 

 

 

Question 02. k 진수에서 소수의 갯수 구하기

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

 

양의 정수 n이 주어집니다. 이 숫자를 k 진수로 바꿨을 때, 변환된 수 안에 특정 조건에 맞는 소수(Prime number)가 몇 개인지 알려주는 프로그램을 작성하는 문제입니다.

 

 

Solution for Question 02

2번 문제도 1번 문제와 비슷하지만 단순히 주어진 자료구조를 이용해서 구현하기 보단 언어에서 제공하는 API나 자료구조를 응용하여 주어진 문제를 어떤식으로 해결할 수 있는지를 보고자 하는 문제였던 것 같았습니다. 

 

먼저 구현해야 할 것은 바로 진법을 어떻게 변환하는 것입니다. n이 1 ~ 1,000,000 길이까지이고, k는 3 ~ 10까지이므로 1,000,000 길이를 3진수로 변환하면 최대 길이는 1,212,210,202,001길이 입니다.실제로 이 길이는 우리가 사용하는 int 범위보다 훨씬 길기 때문에 다른 타입을 이용해서 진법 변환을 수행해야 합니다.

 

간단하게는 String 타입을 이용해볼 수 있습니다. Python 언어라면 일반적인 String을 사용해보거나 list를 사용해볼 수 있을 것입니다. 반면 Java에서는 StringBuilder가 존재하는데, Java의 StringBuilder가 가질 수 있는 최대 capacity는 2147483647 길이라는 점을 감안했을 때 실제로 이 문제를 풀기 위한 최적의 조건은 아닙니다.

 

하지만 아이러니하게도 StringBuilder를 사용했을 때도 잘 풀리긴 합니다.

 

Java의 Integer 클래스에는 toString 메서드가 있습니다. 해당 메서드를 이용하면 StringBuilder를 사용하지 않고도 쉽게 숫자를 특정 진법 값으로 바꿀 수 있습니다. 

 

 

 

Question 03 주차 요금 계산

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

 

주차장의 요금표와 차량이 들어오고(입차) 나간(출차) 기록이 주어졌을 때, 차량별로 주차 요금을 계산하려고 합니다. 문제를 풀기 위한 특정 조건이 주어졌을 때, 차량번호가 작은 자동차부터 청구할 주차 요금을 차례대로 정수 배열에 담아 return 하는 함수를 작성하는 문제입니다.

 

 

Solution for Question 03

개인적으로 3번 문제보다는 2번 문제가 더 쉬웠던 것 같았는데요. 정답률은 73%로 2번 문제 정답률인 55%보다 더 높은 수치입니다. 3번 문제가 2번 문제보다 개인적으로 더 어렵다고 느껴진 것은 복잡한 요구사항 때문이었는데요. 간단하게 풀려고 접근하게 되면 실패 케이스가 많이 나오는 문제였습니다.

 

이 문제를 풀기 위해서는 먼저 입력에 주어진 시간을 정수 타입인 int로 변환하는 함수를 구현해줘야 합니다. 그래야만 입차와 출차를 비교하여 요금을 계산할 수 있기 때문입니다.

 

그런 다음, 각 차량의 주차 시간을 모두 계산합니다. 기본 시간의 경우 기본 시간을 준수하고, 그 외에는 요구사항대로 진행하면 됩니다.

 

마지막으로 주차 요금을 계산합니다. 이 때, 단위 시간보다 미만의 계산이 나오는 경우의 처리가 중요한데요. 이 부분을 잘못 처리하면 단위 시간 미만의 요금에 대해서 추가 요금이 계산되는 오차가 나오기 때문에 반드시 이 부분 처리하는 로직을 넣어줘야 합니다.

 

 

 

Question 04 양궁 대회

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

 

카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원회는 한 선수의 연속 우승보다는 다양한 선수들이 양궁대회에서 우승하기를 원합니다. 따라서, 양궁대회 운영위원회는 결승전 규칙을 전 대회 우승자인 라이언에게 불리하게 특정 조건을 정해놓고, 경길를 진행하려 합니다. 

 

이 때, 라이언이 어피치를 가장 큰 점수차로 이기기 위해 n발의 화살을 어떤 과녁 점수에 맞춰야 하는지를 알려주는 프로그램을 구현하는 문제입니다.

 

 

Solution for Question 04

4번 문제부터 난이도가 어려워집니다. 이 때부터 정답률이 21%로 내려가는데요. 

이 문제는 DFS를 이용하여 풀어 볼 수 있습니다.

 

각자 구한 점수표 중에서 가장 큰 점수차가 나는 점수를 구하기 위해 점수 테이블을 저장하는 클래스를 만들고, Java의 Comparable 인터페이스로 구현합니다. 해당 인터페이스를 구현하는 이유는 Java 언어에서 제공하는 Sort 알고리즘을 이용하기 위함입니다.

 

효율성 테스트 조건이 없기 때문에 중복 조건을 투여해도 좋을 것입니다. 중복 조건이란, visited와 같은 중복 판별 알고리즘 없이 중복 조건을 수용해 그들 데이터 중 가장 높은 점수를 판별하는 것입니다.

 

특정 언어를 깊게 응용하고 알고리즘에 대한 지식이 어느 정도 되는지를 볼 수 있는 문제였습니다.

 

 

 

Question 05 양과 늑대

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

 

이진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수 보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

 

이 때, 제시한 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 구하는 함수를 구현하는 문제입니다.

 

 

Solution for Question 05

이 문제도 4번 문제처럼 DFS를 이용해 문제를 풀어볼 수 있습니다.

 

먼저 각 노드의 집합을 Edge로 표현하고, 그들이 어떻게 이어져 있는지에 대한 정보를 Graph로 표현하였습니다. 이 부분은 여러분들이 편하신대로 구현하시면 됩니다.

 

중요한 것은 DFS 부분입니다. 사실 위 코드는 트리의 각 노드에서 한 번씩만 방문하고 끝나기 때문에 양을 최대로 구할 수 있는 마릿수를 구한다기 보다는 각 트리의 노드를 방문해서 오른쪽과 왼쪽 여부 상관없이 방문만 하면 끝나기 때문에 max 함수를 이용했다 하더라도 정확하게 최대 구할 수 있는 양의 마릿수를 구할 수가 없습니다.

 

따라서 방문할 수 있는 모든 트리의 노드를 추가하고, 해당 노드를 방문하는 형태로 작성하고, 그 다음 노드를 탐색할 때 또 다시 그 노드를 중복 방문할 수 있도록 유도하여야 합니다. 이렇게 하면 모든 방문 형태를 가지기 때문에 별도의 max 함수를 이용하지 않고도 최대로 구할 수 있는 양의 마릿수를 출력해낼 수 있습니다.

 

 

 

Question 06 파괴되지 않은 건물

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

 

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

 

적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 갯수가 몇 개 인지를 알려주는 함수를 구현하는 문제입니다.

 

 

Solution for Question 06

올해 카카오 신입 코딩 테스트에서 효율성을 요구하는 유일한 문제입니다. 언뜻 보면 완전 탐색으로도 쉽게 가능해 보이지만 효율성이 걸려 있기 때문에 완전 탐색인 O(N * M)으로 풀이를 하게 되면 효율성 테스트에 쉽게 망가질 수 있는 문제입니다.

 

스킬이 공격 스킬인지 회복 스킬인지를 확인하고, Dynamic Programming 기법을 통해 해당 스킬이 발동되고 난 후의 matrix를 계산합니다.

이렇게 누적합이 적용된 상태로 matrix를 완전 탐색하여 파괴되지 않은 건물을 스캔하면 효율성 테스트에서 통과를 할 수 없습니다. (시간복잡도: O(N * M * K) )

 

이 문제 풀이의 핵심은 좌 -> 우, 상 -> 하로 누적합을 진행하여 O(K)가 되는 작업을 O(1)로 최적화하는 것입니다. 이렇게만 하면 O(N * M * K)가 O(N * M + K)로 최적화 되기 때문에 효율성 테스트를 쉽게 통과할 수 있습니다.

 

 

 

Question 07 사라지는 벌판

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

 

플레이어 A와 플레이어 B가 서로 게임을 합니다. 당신은 이 게임이 끝날 때까지 양 플레이어가 캐릭터를 몇 번 움직이게 될지 예측하려고 합니다. 

각 플레이어가 1x1 게임 보드에서 특정 조건으로 게임을 수행했을 때, 두 캐릭터가 최적의 플레이로 움직인 횟수의 합을 구하는 함수를 작성하는 문제입니다.

 

 

Solution for Question 07

역대 카카오 신입 코딩 테스트 마지막 문제인 것치곤, 쉬운 조건으로 출제된 문제입니다. 보드가 일단 크지 않고, 플레이어가 지나가면 단순히 그 보드에 있는 판이 사라진다는 조건이기 있기 때문에 탐색 조건이 줄어듭니다. 따라서 이 문제는 DFS 알고리즘을 써서 충분히 해결할 수 있습니다.

 

매판 플레이어의 승패 여부와 움직인 횟수를 확인하는 클래스를 만듭니다. 시작 지점에서 누군가 게임에서 이긴 경우, 이 게임은 빠르게 종료되며 최소 움직인 횟수를 반환하면 됩니다.

 

반대로 플레이어가 먼저 지는 케이스가 발생하는 경우, 진 플레이어가 이동한 횟수 등을 누적한 상태로 반환해주면 됩니다.

 

 

 

마치며...

작년 문제와 비교해봤을 때, 2022년 카카오 신입 1차 코딩 테스트 문제는 난이도가 많이 낮아진 모습입니다. 필요 이상의 난이도가 높은 문제 출제 비중을 줄이고, 기본적인 문제(Lv 1 ~ Lv 2) 수준의 문제를 많이 출제한 뒤, 해당 문제에서 효율성 등을 추가해 변별력을 줌으로써 확실하게 어떤 지원자를 뽑으려 하는지를 맥락이 올해는 유난히 잘 보였던 문제들이었다고 생각합니다.

 

 

참고: 2022 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제 해설

(https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/)