C++ 코딩테스트 강좌, 줄 세우기

문제 설명

N명의 학생들이 교실에서 줄을 서고 있습니다. 각 학생의 키는 배열로 주어지며, 주어진 키 순서와 다르게 서 있을 경우, 학생들은 자신의 위치를 바꿔줄 수 있습니다.
이때, 학생들을 키의 오름차순으로 정렬하기 위한 최소의 스왑 수를 구하는 문제입니다.

입력 형식

첫 번째 줄에 학생의 수 N이 주어집니다. (1 ≤ N ≤ 1000)
두 번째 줄에는 N명의 학생의 키가 공백으로 구분되어 주어집니다. 각 키는 1 이상 1000 이하의 정수입니다.

출력 형식

최소 스왑 수를 출력합니다.

예제 입력/출력

        입력:
        5
        5 3 2 4 1
        
        출력:
        4

문제 풀이

이 문제를 해결하기 위해 우리는 다음 단계를 따릅니다:

1단계: 문제 이해하기

주어진 학생의 키를 오름차순으로 정렬하기 위한 최소 스왑 수를 찾는 것입니다.
예를 들어, 위의 입력에서 학생들은 {5, 3, 2, 4, 1}의 순서로 서 있었고, 이를 {1, 2, 3, 4, 5}로 바꿔야 합니다.
이 과정에서 몇 번의 교환이 필요한지를 세는 것이 목표입니다.

2단계: 접근 방법

최적의 스왑 수를 찾기 위해서는 각 스왑을 통해 배열의 순서를 한 단계씩 정렬하는 것이 효과적입니다.
우리는 다음과 같은 방법으로 이 문제를 해결할 수 있습니다:

  1. 학생들의 키와 그 인덱스를 쌍으로 묶어 주어진 리스트를 정렬합니다.
  2. 각 학생의 현재 위치와 정렬된 위치를 비교합니다.
  3. 스왑을 통해 학생들을 정렬된 위치로 이동해야 하며, 이미 방문한 학생들은 다시 고려하지 않습니다.

3단계: 알고리즘 구현

        #include 
        #include 
        #include 
        
        using namespace std;

        // 구조체 정의: 인덱스와 키를 쌍으로 관리
        struct Student {
            int index;
            int height;
        };

        // 스왑 함수를 정의
        void swap(Student& a, Student& b) {
            Student temp = a;
            a = b;
            b = temp;
        }

        int minSwaps(vector& heights) {
            int n = heights.size();
            vector students(n);
            for (int i = 0; i < n; i++) {
                students[i] = {i, heights[i]};
            }
            
            // 학생들을 키 기준으로 정렬
            sort(students.begin(), students.end(), [](Student a, Student b) {
                return a.height < b.height;
            });
            
            vector visited(n, false);
            int swapCount = 0;
            
            for (int i = 0; i < n; i++) {
                if (visited[i] || students[i].index == i) {
                    continue;
                }
                
                // 사이클의 크기를 계산
                int cycle_size = 0;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = students[j].index;
                    cycle_size++;
                }
                
                if (cycle_size > 0) {
                    swapCount += (cycle_size - 1);
                }
            }
            return swapCount;
        }

        int main() {
            int n;
            cout << "학생 수를 입력하세요: ";
            cin >> n;
            vector heights(n);

            cout << "학생들의 키를 입력하세요: ";
            for (int i = 0; i < n; i++) {
                cin >> heights[i];
            }

            int result = minSwaps(heights);
            cout << "최소 스왑 수: " << result << endl;
            return 0;
        }

4단계: 코드 설명

위의 코드는 C++로 작성된 줄 세우기 문제의 해결 방법을 보여줍니다.

  • 구조체 Student: 인덱스와 학생의 키를 쌍으로 묶어 관리합니다.
  • swap 함수: 두 학생의 정보를 스왑합니다.
  • minSwaps 함수: 최소 스왑 수를 계산하는 주 함수입니다. 학생 리스트를 정렬하고, 각 방문 여부를 체크하여 사이클을 계산합니다.
  • main 함수: 사용자로부터 입력을 받고 결과를 출력하는 주 함수입니다.

5단계: 테스트 및 검증

코드를 작성한 후 다양한 케이스로 테스트를 수행합니다.
다양한 입력을 통해 예상되는 출력과 일치하는지 확인해야 합니다.
예를 들어, 가장 간단한 테스트 케이스를 추가하여 정확성을 검사합니다: 

        입력:
        3
        3 1 2
        
        출력:
        2

추가적으로, 큰 입력을 통해 성능을 확인하는 것도 중요합니다.

결론

이 문제를 통해 스왑과 정렬의 개념, 구조체의 활용 및 알고리즘의 복잡성에 대한 이해를 높일 수 있었습니다.
C++ 코딩테스트에서 자주 출제되는 유형이므로, 충분한 연습을 통해 알고리즘적 사고를 키워야 합니다.

참고자료

© 2023 C++ 코딩테스트 정보 블로그