2021 카카오 신입 공채 1차 코딩 테스트 문제해설: 7개 문제 정답률과 풀이 전략

2021 카카오 신입 개발자 공채 1차 코딩 테스트는 총 7개의 문제로 구성되었으며, 일부 문제는 효율성 테스트를 포함했다. 문제별 정답률과 풀이 전략은 다음과 같다.

1. 아이디 추천 (정답률 57.50%): 7단계의 문자열 처리 규칙을 정확히 구현하는 문제다. 특별한 알고리즘보다는 조건에 맞는 문자열 변환 로직이 핵심이다.
2. 메뉴 리뉴얼 (정답률 25.50%): 최소 2명 이상에게 주문된 메뉴 조합을 찾는 문제다. 모든 조합을 생성하고 개수를 세어 사전 순으로 정렬해 반환한다.
3. 순위 검색 (정답률 정확성 44.07%, 효율성 4.49%): 지원자 정보를 4가지 조건으로 미리 그룹화하고, 점수 기준 오름차순 정렬 후 이진 탐색(lower bound)을 활용해 조건에 맞는 인원수를 효율적으로 계산한다.
4. 합승 택시 요금 (정답률 정확성 9.60%, 효율성 7.45%): 플로이드-워셜 알고리즘을 사용해 모든 지점 간 최단 거리를 구한 뒤, 합승 지점 k에 대해 d[s][k] + d[k][a] + d[k][b]의 최솟값을 탐색한다.
5. 광고 삽입 (정답률 1.23%): 시각을 초 단위로 환산하고 누적 합(prefix sum)을 활용해 광고 구간 내 시청자 누적 재생시간이 가장 긴 시작 시각을 찾는다.
6. 카드 짝 맞추기 (정답률 0.95%): 카드 제거 순서를 고려해 모든 경우의 수(순열)를 탐색하며, 각 단계에서 커서 이동 최소 횟수는 BFS를 이용해 구한다.
7. 매출 하락 최소화 (정답률 0.57%): 트리 구조에서 DFS와 다이나믹 프로그래밍을 활용해 모든 팀에서 최소 1명 이상 참석하면서 매출 손실을 최소화하는 방법을 구한다.