2026 Kakao Group New Crew Recruitment Coding Test Round 1 Problem Explanations
The post explains the first-round coding test for Kakao Group’s 2026 new-crew recruitment, covering seven problems of gradually increasing difficulty; the provided text details the first five. The solutions rely on string processing, simulation, graph traversal, and structural optimization. The main lesson is to exploit each problem’s constraints and identify the right representation before implementing. ## Problem 1: Preventing Spoilers in Important Words - Split the message into space-separated words and record each word’s character interval. - Classify words as spoiler-protected if their interval overlaps any spoiler range. - Store non-spoiler words in a set or hash map to detect duplicates. - Scan protected words from left to right: - Reject words appearing outside spoiler ranges. - Reject words duplicating an already revealed important word. - Count and record valid words. - Later test groups add overlapping spoiler ranges and duplicate words, requiring both types of deduplication. ## Problem 2: Yellow Traffic Lights - Each light repeats a cycle of green, red, and yellow durations. - The task is to find the first time when every light is yellow. - Since cycles repeat, simulation only needs to continue through the least common multiple of all cycle lengths. - Because each duration is at most 20, a bounded simulation is also feasible. - Possible implementations include: - Updating each light’s state every second. - Precomputing states up to the termination time. - Checking directly whether time `t` lies in each light’s yellow interval. - If no simultaneous yellow period occurs within a full combined cycle, the answer does not exist. ## Problem 3: Maximizing the Number of Leaf Nodes - A split of degree `k` consumes one unit of distribution budget and increases the leaf count by `k - 1`. - Since split degrees are limited to 2 and 3, every path product has the form `2^p × 3^q` and must remain within `split_limit`. - Two structural properties simplify the optimization: - Partial splitting can be rearranged so it occurs at only one depth within a consecutive block of equal split degrees. - Blocks of degree-2 splits should be placed above degree-3 blocks because they use less budget for the same eventual frontier size. - Therefore, an optimal tree consists of: - Consecutive layers of 2-way splits. - Followed by consecutive layers of 3-way splits. - At most one partially split layer. - Enumerate feasible pairs `(i, j)` satisfying `2^i × 3^j ≤ split_limit`. - Fully process each layer while budget allows; at the first insufficient layer, perform as many partial splits as possible and calculate the resulting leaf count. ## Problem 4: Virus Pipes - The tree’s edges use one of three pipe types: A, B, or C. - Opening a pipe type infects every currently reachable organism through connected pipes of that type. - Infection is permanent, and reopening the same type consecutively has no effect. - For each possible pipe-opening sequence: - Start a DFS or BFS from all infected organisms. - Traverse only edges of the selected type. - Mark newly reached organisms as infected. - Exhaustive search is practical because the number of pipe openings is at most 10, yielding at most `3^10 = 59,049` sequences. ## Problem 5: Organizing Kakao Apps - Apps are represented by square blocks on a grid. - Pushing one app by one cell can push blocking apps in the same direction. - Apps leaving one edge wrap around to the opposite side, potentially causing further collisions. - Process each command by: - Using the initially pushed app as a BFS seed. - Finding all apps that must move together. - Moving them one cell simultaneously. - Treating clipped apps that cross the boundary as new seeds. - Repeating until no new seeds remain. - Blocks may be larger than one cell, so collisions can propagate across multiple rows and columns. - With grid dimensions and block sizes bounded by 10, direct simulation is sufficiently efficient and terminates because the state space is finite. Overall, the recommended approach is to model each problem according to its mechanics: sets for duplicate word handling, periodicity for traffic lights, structural exchange arguments for tree optimization, exhaustive DFS/BFS for pipe sequences, and layered BFS simulation for grid movement.
Read original(opens in new tab)
