Hello! In this lecture, we will cover how to solve algorithm problems using Kotlin. We will specifically analyze the types of problems that are frequently asked in algorithm tests and discuss how to solve them efficiently.
Problem Description
As office workers who are planning to spend the busiest weekend consider where they can save time, they decided to visit a shopping mall to shop. Each office worker intends to purchase specific items from the mall, represented as _ITEM_. Since each office worker makes impulsive decisions when visiting the mall to buy items, they each have a list of items they wish to purchase, called PrepareItem. If the same item on an office worker’s purchase list has already been sold to another office worker, that office worker cannot purchase that item.
Final Goal: Through the given purchase candidate lists of each office worker, determine which items can be purchased without overlap. Output the list of items that can be purchased without overlap.
Input Format
- The first line of input contains the number of office workers N (1 ≤ N ≤ 100).
- Following that, N lines will contain the list of items that each office worker wishes to purchase, with the number of items being M_i (1 ≤ M_i ≤ 100).
Output Format
Output the list of items that can be purchased by the office workers. The items should be sorted in ascending order, and each item must be displayed without omission.
Approach to Problem Solving
To solve this problem, the following approach can be used:
- Store the list of items for each office worker.
- Utilize a Set data structure to check the availability of each item.
- Iterate through the items requested by each office worker, checking for duplicates and adding the item only if there is no duplication.
- Sort the list of available items in ascending order and output it.
Kotlin Code Implementation
Now let’s write the code to solve the problem.
fun main() {
val n = readLine()!!.toInt()
val itemSets = List(n) { readLine()!!.split(" ").toSet() }
val availableItems = mutableSetOf()
for (itemSet in itemSets) {
for (item in itemSet) {
if (!availableItems.contains(item)) {
availableItems.add(item)
}
}
}
val result = availableItems.sorted()
println(result.joinToString(" "))
}
Code Explanation
1. val n = readLine()!!.toInt() : First, we take the number of office workers as input.
2. val itemSets = List(n) { readLine()!!.split(" ").toSet() } : We store each office worker’s item list in a Set format. By using a Set, we can automatically resolve duplicates.
3. val availableItems = mutableSetOf : We initialize a MutableSet to store the list of items available for purchase.
Now, as we iterate over the list of office workers, we check each office worker’s desired items and add them to the purchasing list only if they have not already been purchased.
Output Result
Finally, we sort and output the list of available items for purchase. When this code is executed, it will produce the correct output for the given sample input.
Post-Problem Solving Checks
1. Understanding Recursive Algorithms – If the way office workers select items is complex, recursion may be needed through depth-first search.
2. Optimization Considering Time – If the input values are large, code performance should be checked to test feasibility.
3. Testing Various Input Values – Check the robustness of the code by inputting different cases.
Conclusion
In this lecture, we have solved a simple algorithm problem. We discussed efficient methodologies for solving algorithm problems using Kotlin and emphasized the importance of selecting appropriate data structures and implementing clear logic through code for each problem.
In the next lecture, we will cover more complex problems that are frequently asked in actual coding tests. We appreciate your interest!