9월 11일 토요일에 진행된 카카오 블라인드 채용의 1차 코딩테스트를 쳐봤다.
문제 수는 총 7문제였고, 시간은 무려 5시간이나 준다... 나는 대략 3시간 반정도 코딩테스트를 쳤고, 총 5문제를 풀었다. 나중을 위해 풀었던 문제를 간략하게 정리해보고자 한다.
문제
1번
문제를 간략하게 설명하면, 게시판 이용자 중 k번 이상 신고를 받은 이용자는 정지가 된다. 그리고 해당 이용자가 정지가 되면, 신고자에게 알림이 간다. 이때, 신고자와 신고를 당한 사람이 담긴 문자열 배열과 정수 k가 주어질 때, 신고자에게 알림이 가는 횟수를 반환하는 문제이다.
단순하게 문자열을 다루는 문제이다. map을 사용하면 아주 쉽게 해결할 수 있다.
2번
이 문제는 10진수 정수가 주어질 때, 이를 k진수로 변환한 후 특정한 규칙에 맞는 소수를 찾는 문제이다. 특정한 규칙을 보니, 0을 기준으로 토큰으로 나누면 되는 문제여서 0을 기준으로 토큰을 나눈 후, 소수를 찾음으로써 문제를 해결하였다.
3번
주차장의 이용 비용을 계산하는 문제이다. 기본 요금과 기본 시간이 있고, 해당 시간을 초과하면 몇분마다 추가 요금이 청구되는 주차장이 있다. 사용자들의 주차장 입/출 기록이 주어질 때, 사용자들의 비용을 계산하는 문제이다. 1번 문제와 마찬가지로 단순하게 문자열을 다루는 문제이다. map을 사용하여 해결하였다.
4번
A와 B가 양궁 대회를 하는데, 점수판은 10점부터 0점까지 있다. A가 먼저 n발을 쏘고 그 후 B가 n발을 쏘는데, 점수를 계산하는 공식은 다음과 같다.
1. 특정 점수에 맞춘 화살의 개수가 많은 사람이 해당 점수를 가져간다. 단, 같다면 A가 가져간다.
2. 둘다 맞춘 횟수가 0이라면, 둘다 점수를 얻지 않는다.
이런 상황에서 B가 A를 가장 큰 점수차이로 이기는 경우를 구해야한다.
나는 조합을 사용하였다. 특정 점수를 노린다 vs 노리지 않는다의 두 가지 경우로 나누고, 만약 노린다면 상대가 맞춘 화살 + 1만큼만 맞춘다.
또한 문제의 조건 중, 경우가 여러개일 경우 작은 점수를 많이 맞춘 쪽을 반환하라고 하였으므로, 낮은 점수를 우선적으로 선택하도록 플로우가 흘러가게 했다.
5번
간단히 설명하면 트리 구조가 주어지고, 각 노드에는 양 혹은 늑대가 있을 때, 최대한 많은 양을 데려오는 문제이다. 처음에는 단순한 위상정렬 문제로 생각하고 풀었는데, 중간에 추가적인 구현이 필요한 부분이 있었다. 위상정렬을 베이스로 진행하되, 양으로 바로 가지 못하고 늑대를 통해가야하는 경우는 모든경우를 탐색하는 방식으로 진행하니 해결되었다.
후기
초반엔 확실히 쉬웠는데, 뒷부분 문제는 어려운게 몇개 있었다. 그런데 많이 아쉬웠던 것이 어려웠다 하더라도, 6번의 경우 분명 이전에 풀어봤던 문제였던것 같은데 못풀었다... 최근에 개발쪽으로 공부를 한다고 알고리즘 공부를 소홀히 하는게 여기서 드러나는 것 같았다. 조금씩이라도 다시 알고리즘 공부를 해야겠다.
