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

• Baekjoon Algorithm Problem: ACM ICPC
• Data Structures and Algorithms
• Books related to Competitive Programming