2021 Kakao New Graduate Recruitment 1st Coding Test Problem Solutions: Accuracy Rates and Solving Strategies for 7 Problems

The 2021 Kakao New Graduate Developer Recruitment 1st Coding Test consisted of a total of 7 problems, with some problems including efficiency tests. The accuracy rates and solving strategies for each problem are as follows.

1. Id Recommendation (Accuracy Rate 57.50%): This problem requires accurately implementing 7 steps of string processing rules. The core is string transformation logic that meets the conditions, rather than a special algorithm.
2. Menu Renewal (Accuracy Rate 25.50%): This problem involves finding menu combinations ordered by at least 2 people. Generate all combinations, count them, sort them in lexicographical order, and return the result.
3. Ranking Search (Accuracy Rate 44.07%, Efficiency 4.49%): Pre-group applicant information by 4 conditions, sort by score in ascending order, and use binary search (lower bound) to efficiently calculate the number of people matching the conditions.
4. Ride Share Taxi Fare (Accuracy Rate 9.60%, Efficiency 7.45%): Use the Floyd-Warshall algorithm to find the shortest distances between all points, then search for the minimum value of d[s][k] + d[k][a] + d[k][b] for each ride-share point k.
5. Ad Insertion (Accuracy Rate 1.23%): Convert times to seconds and use a prefix sum to find the start time with the longest cumulative viewing time within the ad interval.
6. Card Matching (Accuracy Rate 0.95%): Explore all permutations considering the order of card removal, and use BFS to find the minimum number of cursor moves at each step.
7. Minimizing Sales Drop (Accuracy Rate 0.57%): Use DFS and dynamic programming on a tree structure to find the method that minimizes sales loss while ensuring at least one person from every team attends.