Category: Python Coding Test

div>

Problem Description

There are N students, each having an integer height (the height can range from 1 to 200).
We want to line up these students in ascending order based on their heights.
Given the students’ heights, the problem is to determine the minimum number of swaps needed to arrange the students in order.
A swap refers to exchanging the positions of two students.

Input Format

  • The first line contains the number of students N. (1 ≤ N ≤ 200)
  • The next line contains the students’ heights separated by spaces.

Output Format

Print the minimum number of swaps.

Example

Input

5
5 3 1 4 2

Output

4

Solution

To solve this problem, we can sort the given array and calculate the number of swaps needed.
The basic idea is to compare the number at the current position with its position in the sorted array to perform the swaps.
By utilizing cycles in this process, we can compute the minimum number of swaps required.

Approach

1. Sort the students’ heights to find the ideal order.
2. Compare the current array with the sorted array to identify each height’s current index and target index.
3. Traverse each element and check if it has been visited. For unvisited elements, explore the cycle to calculate
its size. If the size of each cycle is k, then the number of swaps needed is (k – 1).
4. Repeat this process for all elements to calculate the final number of swaps.

Code Implementation

def min_swaps(arr):
    n = len(arr)
    # Create a sorted array and combine it with index information.
    sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])
    
    # Initialize visited array and swap count.
    visited = [False] * n
    swap_count = 0
    
    for i in range(n):
        # Skip already visited indices.
        if visited[i] or sorted_arr[i][0] == i:
            continue
        
        # Explore the cycle.
        cycle_size = 0
        j = i
        
        while not visited[j]:
            visited[j] = True
            j = sorted_arr[j][0]
            cycle_size += 1
            
        if cycle_size > 0:
            swap_count += (cycle_size - 1)
    
    return swap_count

# Take input.
N = int(input())
arr = list(map(int, input().split()))

# Print the result.
print(min_swaps(arr))

Explanation

This algorithm has a time complexity of O(N log N) and calculates the number of swaps based on
the size of cycles using the indices of the sorted array.
Thus, it provides an efficient way to compute all swaps.

Time Complexity Analysis

– It takes O(N log N) time to sort the array.
– In the worst case, visiting all elements once to calculate cycles takes O(N) time.
Thus, the overall time complexity of the algorithm is O(N log N).

Space Complexity Analysis

– O(N) space is needed for the sorted array, and the visited array also requires O(N) space.
Thus, the overall space complexity is O(N).

Conclusion

Through this problem, we learned a method to minimize swaps, which is more than just a simple sorting problem in algorithms.
By utilizing sorting and the cycle approach, we can develop efficient solutions.
It’s important to cultivate problem-solving skills through engineering thinking, so I encourage you to practice more with other examples.

References

Python Coding Test Course, Jumong’s Command

1. Problem Overview

This coding test problem is to implement the given conditions based on the orders that Jumong gave to his soldiers. The problem is as follows.

Problem Description

Jumong gives each soldier N commands. Each command instructs them to move in a specific direction.
The soldiers receive and execute these commands. However, Jumong made a mistake during the command process and decided to ignore some commands.
Now, you need to write a program that calculates the final position based on the executed commands by the soldiers.

Format of Commands

  • The commands are given as a list of strings: ["U", "D", "L", "R"].
  • “U” means to move up by one step, “D” means to move down by one step, “L” means to move left by one step, and “R” means to move right by one step.
  • The number of commands is 1 ≤ N ≤ 1000.

Input

The first line contains the number of commands N,
and the next N lines contain each command.

Output

Output the coordinates of the final position (x, y) as integers.
The initial position is (0, 0).

2. Problem Solving Process

2.1. Understanding the Problem

To solve the problem, we need to implement the movement according to each command following specific rules.
The list of commands will be analyzed, and the coordinates will be updated according to each command.

2.2. Data Structure Design

We use the (x, y) coordinates to store the final position.
It is initialized with x = 0, y = 0.

2.3. Algorithm Design

We will read each command line by line and move in the corresponding direction.
In other words, the coordinates will be updated as follows based on each command:

  • "U": y += 1
  • "D": y -= 1
  • "L": x -= 1
  • "R": x += 1

2.4. Final Code Implementation

def final_position(commands):
    x, y = 0, 0  # Initial position

    for command in commands:
        if command == "U":
            y += 1
        elif command == "D":
            y -= 1
        elif command == "L":
            x -= 1
        elif command == "R":
            x += 1

    return (x, y)

# Example input
N = int(input("Enter the number of commands: "))
commands = [input().strip() for _ in range(N)]
# Output final position
print(final_position(commands))

3. Examples and Tests

3.1. Test Cases

For example, if the following input is given: 

5
    R
    R
    U
    D
    L

When processing the above commands, the final position will be (1, 0).

4. Conclusion

In this process, we implemented an algorithm to calculate the final position of the soldiers based on Jumong’s commands.
We solved the problem through coordinate updates according to each command.
This simple problem helps us understand the basics of data structures and algorithm application.

Python Coding Test Course, Exploring Combinations

Many people preparing for coding tests find it important to understand various concepts of algorithms and to develop the skills necessary to solve problems. Today, we will explore the concept of ‘combination’ and examine the problem-solving process using this concept.

1. Understanding Combination

A combination represents the number of ways to choose r elements from a given set of n elements, without regard to the order of selection. The formula for calculating the number of combinations is as follows:

C(n, r) = n! / (r! * (n – r)!)

Here, n! denotes n factorial, and n! = n × (n – 1) × (n – 2) × … × 1. Combinations are generally denoted as ‘nCr’, meaning “choosing r out of n”.

Examples of Combinations

For example, suppose we have four elements {A, B, C, D}. The combinations of selecting two from these are as follows:

  • AB
  • AC
  • AD
  • BC
  • BD
  • CD

2. Problem Introduction

Now, let’s solve a problem using combinations. The problem is as follows:

Problem: Given a list of integers, choose k numbers and print all possible combinations.

Input:

  • The first line contains n (1 ≤ n ≤ 20) and k (1 ≤ k ≤ n).
  • The second line contains n integers. These integers are positive integers between 1 and 100.

Output:

  • Print all combinations in ascending order, with each combination on a new line.

3. Problem Solving

To meet the requirements of the problem, we will follow these steps:

3.1 Input Handling

First, we receive inputs for n and k, as well as n integers. We store these values in an appropriate data structure.

3.2 Generating Combinations

To generate combinations, we can use the combinations function from Python’s itertools module. This function generates all combinations of r selections from a given iterable.

3.3 Printing Combinations

After generating the combinations, we sort them and print each combination.

4. Code Implementation

Now, let’s implement the actual code. Below is the Python code written based on the above logic:


import itertools

def generate_combinations(nums, k):
    # Generate k combinations and sort them
    combinations = list(itertools.combinations(sorted(nums), k))
    return combinations

if __name__ == "__main__":
    # Input handling
    n, k = map(int, input("Enter n and k (e.g., 4 2): ").split())
    nums = list(map(int, input(f"Enter {n} integers: ").split()))

    # Generate combinations
    result = generate_combinations(nums, k)

    # Print results
    for combo in result:
        print(" ".join(map(str, combo)))

5. Code Explanation

The above code works as follows:

  • It receives n and k as input from the user.
  • It inputs n integers and stores them in a list.
  • It generates k combinations using itertools.combinations.
  • It sorts and prints the generated combinations.

6. Test Cases

Let’s test the code with various inputs:

Input Example 1:

4 2

1 2 3 4

Output Example 1:

1 2

1 3

1 4

2 3

2 4

3 4

Input Example 2:

5 3

5 1 3 2 4

Output Example 2:

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

7. Conclusion

Today, we learned about the important concept of ‘combinations’ in coding tests and practiced solving a problem using this concept. Combinations are frequently used in various algorithmic problems, so it is important to understand the basic concepts and methods of utilization. I hope this tutorial helps you understand the concept of combinations and develop better skills in using Python. I encourage you to continue building your skills through various algorithm problems!

python coding test course, finding non-squares

Hello, everyone! In this blog post, we will solve an algorithm problem called Finding Non-Square Numbers. This problem is one of the types that frequently appear in coding tests, requiring both mathematical thinking and programming skills. In this article, we will explain the problem description, solution ideas, actual code, and time complexity analysis in detail.

Problem Description

Given a natural number N, write a function to count the number of natural numbers that are not perfect squares among the natural numbers from 1 to N. A perfect square is a number that can be expressed in the form x * x = y for some natural number x. For example, 1 (1 * 1), 4 (2 * 2), 9 (3 * 3), and 16 (4 * 4) are perfect squares.

Input

  • A natural number N (1 ≤ N ≤ 106)

Output

  • Print the count of numbers that are not perfect squares.

Example

Input

N = 10

Output

7

Explanation: The natural numbers from 1 to 10 are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Among these, 1, 4, and 9 are perfect squares, so there are 10 – 3 = 7 numbers that are not perfect squares.

Solution Idea

To solve this problem, we must follow these steps:

  1. Check whether each natural number from 1 to N is a perfect square.
  2. Count the number of perfect squares and subtract this from N to get the count of non-square numbers.

To find perfect squares, we can square integers from 1 to √N and precompute the perfect squares from 1 to N, then count the number of perfect squares and subtract this from N. This allows us to solve the problem with a time complexity of O(√N).

Implementation

Now, let’s write the code to solve the problem in Python. Below is a function that counts the number of non-square numbers:


import math

def count_non_squares(N):
    if N < 1:
        return 0
    
    # Calculate the number of perfect squares
    square_count = int(math.sqrt(N))
    
    # Count of non-perfect square numbers
    return N - square_count

Code Explanation

  • First, we use math.sqrt(N) to calculate the square root of N. This provides basic information to know how many perfect squares are there among the natural numbers less than or equal to N.
  • Next, we use int() to convert the square root to an integer, representing the count of perfect squares.
  • Finally, we subtract the count of perfect squares from N to print the count of non-perfect square numbers.

Time Complexity Analysis

The time complexity of this problem is O(1). Even when N is large, calculating the square root can be done quickly. Therefore, this algorithm is very efficient.

Conclusion

In this post, we covered the problem of finding non-square numbers. This problem requires simple mathematical thinking and can help cultivate efficient algorithm coding skills for problem-solving. Since it is a type of problem frequently encountered in coding tests, be sure to practice well!

In the next lecture, we will tackle more interesting problems. Thank you!

python coding test course, picking up pebbles

In this post, we will explore problem-solving methods commonly encountered in Python coding tests through an algorithm problem called “Picking Up Pebbles.” We will define the problem, establish a solution strategy, and ultimately provide Python code.

Problem Description

You discovered pebbles while walking along the beach. Each pebble has a different weight. When picking up pebbles, you must pick up two pebbles at a time, and the maximum number you can pick is N.

Your goal is to calculate the minimum number of times you need to pick up to remove all the pebbles’ weights. Additionally, the weights of the pebbles you pick must be selected from those that have not been picked before.

Input Format

The input follows this format:

  • The first line contains the number of weights N.
  • The second line contains the weights of N.

The output should return the minimum number of times you need to pick up to remove all the pebbles’ weights.

Example

Input:
5
1 2 3 4 5

Output:
3

Problem Analysis

When picking the weights of the pebbles, we can pick two pebbles at a time, but we need to choose the weights we pick as diversely as possible. Therefore, to efficiently pick the given weights, we need to include all weights through the smallest number of picks.

Solution Strategy

This problem can be simply explained as a combination problem. Since we can pick two pebbles at a time with each pick, we need to consider half the number of weights. Counting the weights of each pebble and calculating the number of picks based on the count of weights is essential.

Algorithm Implementation

You can solve the problem based on the following algorithm:

  1. Read the number of weights N.
  2. Store each pebble’s weight in a list.
  3. Count the weights of the pebbles.
  4. Calculate the minimum number of picks by rounding up half the number of weights.

Python Code Implementation

The code below implements the above algorithm in Python:

import math

def min_pickups(weights):
    unique_weights = set(weights)
    return math.ceil(len(unique_weights) / 2)

# Taking input
N = int(input("Please enter the number of weights: "))
weights = list(map(int, input("Please enter the weights of the pebbles: ").split()))
result = min_pickups(weights)
print("Minimum number of picks required to remove all pebbles:", result)

Code Explanation

The provided code first defines the min_pickups function. This function calculates the number of unique pebble weights from the input, then returns the final result by rounding up half of that number.

In the main part, it takes user input to create a list containing the weights and passes this list to the min_pickups function to output the results.

Conclusion and Tips

In this tutorial, we learned problem-solving methods for Python coding tests through the “Picking Up Pebbles” problem. Algorithm problems often involve combinations and ordering, so when solving such problems, it’s essential to effectively count weights and construct combinations.

I hope to deepen my understanding of algorithms through various problems in the future. I will continue to provide useful problem-solving methods and coding tips next time as well. Thank you!