카카오, 2021 인턴십 코딩 테스트 5문제 해설 공개

카카오가 2021년 5월 8일 진행된 여름 인턴십 코딩 테스트의 5개 문제에 대한 공식 해설을 공개했다. 이번 테스트는 난이도별로 배치된 5문제로 구성되었으며, 일부 문제에는 효율성 테스트 케이스가 포함되어 최적화된 알고리즘 구현이 요구됐다.

문제별 핵심 풀이 전략

문제 1 (숫자 문자열과 영단어): 영단어로 된 숫자를 정수로 변환하는 문제로, 문자 단위 처리나 replace 함수 활용 접근이 제시됐다.

문제 2 (거리 두기 확인하기): 5x5 대기실에서 응시자 간 맨해튼 거리가 2 이하일 때 파티션으로 차단되어 있는지 확인하는 문제다. DFS/BFS 또는 단순 반복문을 통해 인접 조건을 검증한다.

문제 3 (표 편집): 행 삭제 및 복구가 가능한 표 편집 시뮬레이션이다. 정확성 테스트에서는 배열을 사용하되, 효율성 테스트(n 최대 100만)에서는 링크드 리스트 또는 세그먼트 트리/펜윅 트리를 활용해 명령어를 효율적으로 처리한다.

문제 4 (미로 탈출): 함정(trap)에 따라 간선 방향이 역전되는 그래프에서 최단 경로를 찾는 문제다. 함정 노드 수가 최대 10개이므로, 그래프 상태를 비트마스크로 표현하여 다익스트라 알고리즘을 적용한다.

문제 5 (시험장 나누기): 이진 트리 구조의 시험장을 k개 그룹으로 나누어 최대 그룹 인원을 최소화하는 문제다. 효율성 테스트에서는 파라메트릭 서치(이분 탐색)와 다이나믹 프로그래밍(DP)을 조합하여 해결한다.