문제 설명
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단계: 접근 방법
최적의 스왑 수를 찾기 위해서는 각 스왑을 통해 배열의 순서를 한 단계씩 정렬하는 것이 효과적입니다.
우리는 다음과 같은 방법으로 이 문제를 해결할 수 있습니다:
- 학생들의 키와 그 인덱스를 쌍으로 묶어 주어진 리스트를 정렬합니다.
- 각 학생의 현재 위치와 정렬된 위치를 비교합니다.
- 스왑을 통해 학생들을 정렬된 위치로 이동해야 하며, 이미 방문한 학생들은 다시 고려하지 않습니다.
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++ 코딩테스트에서 자주 출제되는 유형이므로, 충분한 연습을 통해 알고리즘적 사고를 키워야 합니다.