정수로 이루어진 배열이 주어졌다고 가정해 봅시다. 우리는 단 한 번의 스왑(swap) 연산만 사용해서 배열의 값들을 비내림차순(오름차순과 동일하게 취급)으로 정렬할 수 있는지 판단해야 합니다. 가능하다면 "정렬할 수 있다"고 답하고, 그렇지 않다면 "정렬할 수 없다"고 답하면 됩니다.
예를 들어 입력 리스트가 [7, 8, 12, 10, 11, 9]라면, 출력은 "Can be done"(정렬 가능)이 됩니다.
해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
temp_list: 입력 리스트input_list의 복사본을 만듭니다.temp_list를 오름차순으로 정렬합니다.swap_count := 0으로 초기화합니다.- 0부터 입력 리스트의 크기까지 반복하면서 다음을 수행합니다.
- 만약
input_list[i]가temp_list[i]와 같지 않다면,swap_count를 1 증가시킵니다.
- 만약
- 반복이 끝난 후:
swap_count가 0이면 이미 정렬된 상태이므로 True를 반환합니다.swap_count가 2이면 서로 위치가 바뀐 두 원소를 한 번의 스왑으로 교환할 수 있으므로 True를 반환합니다.
- 그 외의 경우(위치가 어긋난 원소가 3개 이상인 경우)에는 False를 반환합니다.
핵심 아이디어
정렬된 배열과 원본 배열을 비교했을 때, 위치가 다른 원소가 정확히 2개라면 그 두 원소를 맞바꾸는 것만으로 정렬이 완성됩니다. 위치가 다른 원소가 없다면(0개) 이미 정렬된 상태이고요. 하지만 3개 이상이라면 한 번의 스왑으로는 절대 정렬할 수 없습니다.
구현 예제
from copy import deepcopy
def solve(input_list):
temp_list = deepcopy(input_list)
temp_list.sort()
swap_count = 0
for i in range(len(input_list)):
if input_list[i] != temp_list[i]:
swap_count += 1
if swap_count == 0 or swap_count == 2:
print("Can be done")
else:
print("Can't be done")
input_list = [7, 8, 12, 10, 11, 9]
solve(input_list)입력
[7, 8, 12, 10, 11, 9]
출력
Can be done
동작 과정 살펴보기
입력 리스트 [7, 8, 12, 10, 11, 9]를 정렬하면 [7, 8, 9, 10, 11, 12]가 됩니다. 두 리스트를 인덱스별로 비교해 보면 인덱스 2와 5의 값(12와 9)만 서로 다릅니다. 즉, 위치가 어긋난 원소가 정확히 2개이므로 이 두 값을 한 번 스왑하면 정렬된 배열을 얻을 수 있습니다.
이 알고리즘은 정렬에 O(n log n), 비교에 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n log n)입니다.