Category: Kotlin coding test

In the process of preparing for coding tests using Kotlin, one of the problems many face is understanding and solving various algorithmic problems. In this course, we will learn how to easily understand and solve problems based on ancient narratives related to Jumong by solving an economical algorithm problem titled ‘Jumong’s Command’.

Problem Description

Jumong commanded his army to defeat the enemies in the north and establish his kingdom. His command instructed each soldier to take a specific action. In this problem, when there are N soldiers, we need to determine what action each soldier will take.

The problem is as follows:

Problem: Jumong’s Command

Jumong has N soldiers. Each soldier is represented by a random number from 1 to 100, and Jumong commands soldiers with even numbers to “Move forward!” and those with odd numbers to “Step back!”.

Write a program that counts the number of even and odd soldiers from the given list of N soldier numbers and outputs each command.

Input

    The first line contains the number of soldiers N (1 ≤ N ≤ 1000).
    The second line contains N soldier numbers separated by spaces.
    

Output

    Print the commands based on each soldier's even/odd status.
    Output "Move forward!" or "Step back!" over N lines.
    

Example Input

5
1 2 3 4 5
    

Example Output

Step back!
Move forward!
Step back!
Move forward!
Step back!
    

Problem Solving Process

Now let’s look at how to solve this problem step by step. We will use Kotlin to solve it.

Step 1: Get Input

First, we need to receive input from the user. We can use the readLine() function to get the input values.

Step 2: Convert to Number List

Since the entered numbers are separated by spaces, we need to convert them into a list. We will use Kotlin’s split() method to split by spaces.

Step 3: Determine Even/Odd and Print Commands

Now, we can loop through all soldiers, check whether each number is even or odd, and print the corresponding command. We can use Kotlin’s if statement to evaluate the conditions.

Code Example

fun main() {
    // Step 1 - Get Input
    val n = readLine()!!.toInt()  // Number of soldiers
    val soldiers = readLine()!!.split(" ").map { it.toInt() }  // List of soldier numbers

    // Step 3 - Determine Even/Odd and Print Commands
    for (soldier in soldiers) {
        if (soldier % 2 == 0) {
            println("Move forward!")
        } else {
            println("Step back!")
        }
    }
}
    

Summary of the Entire Process

The process of solving the problem can be summarized as follows:

1. Read the given input.
2. Convert the entered numbers into a list.
3. Determine the even/odd status of each soldier and print the commands.

Conclusion

Through this course, we learned how to solve the Jumong’s Command problem and how to use Kotlin. Algorithm problems can be presented in various forms, and understanding the fundamental problem-solving structure and approach is essential. Let’s continue to enhance our algorithm skills by practicing different problems!

1. What is Combination?

A combination refers to the number of ways to select a specific number of elements from a given set.
For example, the combinations of picking 2 elements from {A, B, C} are AB, AC, and BC.
Since combinations do not consider the order, {A, B} and {B, A} are regarded as the same combination.

2. Problem Definition

We will solve the following problem.

Problem Description

Given an integer array nums and an integer k,
the problem is to generate combinations by picking k elements from the nums array.
Return the combinations in the form of a list of lists.

Input Example

        nums = [1, 2, 3, 4]
        k = 2
    

Output Example

        [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    

3. Algorithm Approach

There are several methods to generate combinations, but
the simplest and most representative method is to use backtracking.
This method explores all possible cases while
generating combinations based on basic conditions.

4. Implementation in Kotlin

Let’s implement the algorithm described earlier in Kotlin.

fun combine(nums: IntArray, k: Int): List> {
        val result = mutableListOf>()
        backtrack(result, mutableListOf(), nums, k, 0)
        return result
    }

    fun backtrack(result: MutableList>, tempList: MutableList, nums: IntArray, k: Int, start: Int) {
        // If the size of the combination is equal to k, add it to the result
        if (tempList.size == k) {
            result.add(ArrayList(tempList))
            return
        }
        // Generate combinations
        for (i in start until nums.size) {
            tempList.add(nums[i])
            backtrack(result, tempList, nums, k, i + 1)
            tempList.removeAt(tempList.size - 1)
        }
    }

    // Example usage
    fun main() {
        val nums = intArrayOf(1, 2, 3, 4)
        val k = 2
        val combinations = combine(nums, k)
        println(combinations)
    }

5. Code Explanation

The code above is structured as follows.

• combine: The main function initializes a list to store results and a temporary list to store combinations, and calls the backtracking function.
• backtrack: A function that recursively generates combinations. If the current combination size is equal to k, it adds to the result list; otherwise, it repeats by adding the next element.

6. Complexity Analysis

The time complexity of this algorithm is proportional to the number of combinations.
In the worst case, it has a time complexity of O(N^K),
and the space complexity is O(K).

7. Conclusion

The problem of generating combinations is frequently encountered in coding tests.
The backtracking technique can effectively solve combination generation problems.
Based on what you learned today, I hope you will practice various combination problems.

Problem Description

The pebble extraction problem is about extracting a given number of pebbles according to specific rules.
Each pebble has a specific weight, and we can extract them according to two rules:

• A pebble can be extracted if its weight is less than or equal to X.
• When a pebble is extracted, its weight becomes 0 and affects the surrounding pebbles.

Problem Input

The first line contains the number of pebbles N (1 ≤ N ≤ 100,000) and the weight limit X (1 ≤ X ≤ 10,000).
The second line lists the weight of each pebble separated by spaces. (1 ≤ weight ≤ 10,000)

Example

        Input:
        5 5
        4 5 3 2 1

        Output:
        5
    

Problem Solving Process

To solve this problem, the following steps are needed:

Step 1: Problem Analysis

It is a problem of comparing the weights of the given pebbles.
We can select pebbles that are less than or equal to X, and we need to calculate how many pebbles we can extract.
In the given example, the pebble weights are [4, 5, 3, 2, 1] and X is 5.
Thus, there are 5 pebbles with weights less than or equal to X (i.e., 5).
As a result, we can extract 5 pebbles.

Step 2: Algorithm Design

The algorithms that can be used to solve the problem are as follows:

• Count the number of input pebbles and check the weight of each pebble.
• Count the pebbles with weights less than or equal to X.
• Finally, output the counted number.

Step 3: Kotlin Code Implementation

Below is the code implemented in Kotlin based on the above algorithm:

        
        fun main() {
            val input = readLine()!!.split(" ").map { it.toInt() }
            val n = input[0]
            val x = input[1]

            val weights = readLine()!!.split(" ").map { it.toInt() }
            val count = weights.count { it <= x }

            println(count)
        }
        
    

Step 4: Time Complexity Analysis

The time complexity of this algorithm is O(N).
The time complexity is determined by the number of pebbles input since we need to check each pebble’s weight.

Conclusion

The pebble extraction problem is a basic algorithm problem that involves filtering data based on conditions.
Using Kotlin allows for a concise solution to such problems and serves as good study material for practicing fundamental data processing skills.