카카오, 2020 신입 개발자 1차 코딩 테스트 문제 및 풀이 공개

카카오가 2020년 신입 개발자 채용을 위한 1차 코딩 테스트의 7개 문제와 상세 풀이를 공개했다. 테스트는 지난 7일 5시간 동안 진행되었으며, C++, Java, Python 등 6가지 언어 중 하나를 선택해 응시할 수 있었다.

문제는 난이도 순으로 배치되었으며, 효율성 테스트가 포함된 4번 문제를 제외하면 모든 테스트 케이스를 통과해야 정답으로 인정된다. 공개된 해설에는 각 문제의 출제 의도와 최적화된 알고리즘 접근법이 담겼다.

주요 문제 유형 및 해설

• 문자열 압축 (1번): 문자열을 특정 단위로 잘라 반복되는 부분을 숫자로 표현하는 방식으로, 가장 짧은 압축 길이를 구하는 문제다. 제한된 입력 크기(1,000 이하)로 인해 완전 탐색이 가능하다.
• 괄호 변환 (2번): 주어진 알고리즘에 따라 균형 잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하는 문제다. 재귀 함수를 활용한 구현 능력이 평가 포인트다.
• 자물쇠와 열쇠 (3번): 2차원 배열을 회전하고 이동시켜 자물쇠의 홈을 모두 채울 수 있는지 판단하는 문제다. 배열 회전 함수를 활용해 가능한 모든 경우의 수를 탐색한다.
• 가사 검색 (4번): 와일드카드 '?'가 포함된 패턴으로 단어를 검색하는 문제다. 정확성 풀이는 단순 비교지만, 효율성 통과를 위해 트라이(Trie) 자료구조나 이분 탐색을 사용해야 한다. 특히 접두사/접미사 패턴에 대응하기 위해 문자열을 뒤집어 두 개의 트라이를 구성하는 방식이 제시됐다.
• 기둥과 보 설치 (5번): 규칙에 따라 기둥과 보를 설치하거나 삭제했을 때 구조가 유효한지 시뮬레이션하는 문제다. 삭제 시 남은 구조물이 규칙을 만족하는지 확인하는 로직이 핵심이다.
• 외벽 점검 (6번): 원형 외벽의 취약 지점을 최소한의 친구로 점검하는 문제다. 원형을 직선으로 펼치는 배열 회전 기법과 순열(permutation)을 활용해 최적해를 찾는다.
• 무인도 이동 (7번): 2x1 크기의 로봇이 벽을 피해 목적지까지 이동하는 최소 시간을 구하는 문제다. 로봇의 위치와 방향을 상태(state)로 정의하여 BFS를 수행하며, 회전 시 충돌 여부를 정밀하게 판별해야 한다.