문제 설명
N명의 학생이 있고, 각 학생은 정수형 키(키의 길이는 1 이상 200 이하)를 가지고 있다.
이 학생들을 키의 오름차순으로 줄을 세우려고 한다.
학생들의 키가 주어졌을 때, 학생들을 줄 세우기 위해 최소 몇 번의 자리 바꿈이 필요한지를 구하는 문제이다.
자리 바꿈이란 두 학생의 위치를 서로 바꾸는 것을 의미한다.
입력 형식
- 첫 줄에 학생의 수 N이 주어진다. (1 ≤ N ≤ 200)
- 다음 줄에 학생들의 키가 공백으로 구분되어 주어진다.
출력 형식
최소의 자리 바꿈 횟수를 출력한다.
예제
입력
5
5 3 1 4 2
출력
4
문제 풀이
이 문제를 해결하기 위해서는 주어진 배열을 정렬하고, 각 자리 바꿈의 수를 계산하는 방법을 사용할 수 있습니다.
기본적인 아이디어는, 현재 위치에 있는 숫자와 정렬된 상태에서의 위치를 비교하여 자리 바꿈을 이루는 것입니다.
이 과정에서 사이클을 활용하여 최소의 자리 바꿈을 계산할 수 있습니다.
접근 방법
1. 학생들의 키를 정렬하여 이상적인 순서를 구합니다.
2. 현재 배열과 정렬된 배열을 비교하여 각 키의 현재 인덱스와 목표 인덱스를 파악합니다.
3. 각 요소를 순회하며, 이미 방문한 요소인지 확인합니다. 방문하지 않았던 요소에 대해 사이클을 탐색하여
사이클의 크기를 계산합니다. 각 사이클의 크기가 k일 경우, 자리 바꿈 수는 (k – 1) 입니다.
4. 모든 요소에 대해 이 과정을 반복하여 최종적인 자리 바꿈 수를 계산합니다.
코드 구현
def min_swaps(arr):
n = len(arr)
# 정렬된 배열을 만들고 인덱스 정보를 합칩니다.
sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])
# 방문 배열과 자리 바꿈 수를 초기화합니다.
visited = [False] * n
swap_count = 0
for i in range(n):
# 방문한 적이 있는 인덱스는 건너뜁니다.
if visited[i] or sorted_arr[i][0] == i:
continue
# 사이클을 탐색합니다.
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
# 입력을 받습니다.
N = int(input())
arr = list(map(int, input().split()))
# 결과를 출력합니다.
print(min_swaps(arr))
해설
이 알고리즘은 O(N log N)의 시간 복잡도를 가지고 있으며, 정렬된 배열의 인덱스를 사용하여
사이클의 크기를 기반으로 자리 바꿈의 수를 계산합니다.
따라서 모든 자리 바꿈을 계산하는 효율적인 방법을 제공합니다.
시간 복잡도 분석
– 정렬하는 데 O(N log N) 시간이 소요됩니다.
– 최악의 경우 모든 요소에 대해 한 번씩 방문하여 사이클을 계산하는 데 O(N) 시간이 소요됩니다.
따라서 전체 알고리즘의 시간 복잡도는 O(N log N)입니다.
공간 복잡도 분석
– 정렬된 배열을 위한 O(N) 공간이 필요하며, 방문 배열도 O(N) 공간을 요구합니다.
따라서 전체 공간 복잡도는 O(N)입니다.
결론
이번 문제를 통해 알고리즘에서는 단순한 정렬 문제가 아닌 자리 바꿈을 최소화하는 방법을 배우게 되었습니다.
배열의 정렬과 사이클 접근법을 활용하여 효율적인 해결책을 개발할 수 있습니다.
공학적 사고를 통한 문제 해결 능력을 기르는 것이 중요하니, 다른 예제들을 통해 더 많은 연습을 하기를 바랍니다.
참고 자료
- 백준 알고리즘 문제: ACM ICPC
- 자료구조와 알고리즘
- Competitive Programming 관련 서적