C++ Coding Test Course, Card Sorting

In recent years, programming and algorithm problem-solving skills have become a crucial assessment criterion not only in the IT industry but also in various fields. In this course, we will learn basic manipulation processes, algorithm design, and optimization through the problem of ‘Card Sorting’. This problem helps enhance understanding of important sorting algorithms in practical work and coding tests.

Problem Description

In old card games, sorting the numbers on cards was essential. You have N cards, each with an integer written on it. You need to sort these cards in ascending order. However, there are some rules in this process:

  • The cards consist of integers and must be arranged in sorted order.
  • The number of cards N (1 ≤ N ≤ 10^6).
  • The numbers written on the cards are integers within the range of -10^9 ≤ number ≤ 10^9.

Input Format

The first line contains the number of cards N, followed by N lines, each containing the number on each card.

Output Format

After sorting the cards in ascending order, print each card’s number on a new line.

Example

Input:
5
3
1
4
1
5

Output:
1
1
3
4
5

Problem-Solving Strategy

This problem is a sorting problem, and various sorting algorithms can be used. However, considering the given range, it is advisable to use basic sorting algorithms such as Quick Sort or Merge Sort. In this course, we will demonstrate how to efficiently solve the problem using the std::sort function included in the C++ STL.

STL Standard Library’s sort() Function

The standard template library (STL) of C++ includes the sort() function. This function sorts the elements of the container provided as an argument. std::sort has an average time complexity of O(N log N) and is very efficient.

Code Implementation


#include <iostream>
#include <vector>
#include <algorithm> // Include to use sort()

int main() {
    int N;
    std::cin >> N; // Input the number of cards
    std::vector<int> cards(N); // Create a vector to store card numbers

    // Input card numbers
    for (int i = 0; i < N; i++) {
        std::cin >> cards[i];
    }

    // Sort card numbers
    std::sort(cards.begin(), cards.end());

    // Output sorted card numbers
    for (int i = 0; i < N; i++) {
        std::cout << cards[i] << std::endl;
    }

    return 0;
}

Code Analysis

The code above consists of the following processes:

  1. Library Inclusion: Includes #include <iostream>, #include <vector>, #include <algorithm> to add basic libraries for input, output, and sorting.
  2. Input: Inputs the number of cards N from the user, and then stores the N card numbers in the vector.
  3. Sorting: Uses the std::sort() function to sort the card numbers stored in the vector in ascending order. Here, the begin() and end() methods are used to set the start and end positions.
  4. Output: Prints the sorted card numbers.

Time Complexity Analysis

The std::sort() function mentioned above operates with an average complexity of O(N log N). This is very efficient for processing large amounts of data. When the input size N is up to 10^6, sorting can be executed within a sufficient timeframe.

Conclusion

In this course, we learned the process of solving the card sorting problem. We were able to write simple yet efficient code utilizing the STL’s sort() function to solve the problem. Such sorting algorithms are frequently used in many programming problems and real situations, so it is important to master and apply them.

In the next session, we will further enhance your coding test skills through additional algorithm problems.

Thank you!