라벨을 정렬 상태로 되돌리는 최소 교환 횟수
자바스크립트 코딩테스트 문제로 permutation-cycles 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
간단한 교환만 허용될 때, 라벨 배열을 오름차순으로 정렬하는 데 필요한 최소 교환 횟수를 구하세요.
문제 설명
서로 다른 정수가 담긴 배열 labels가 주어집니다.
한 번의 교환에서는 배열의 아무 두 위치나 선택해 값을 맞바꿀 수 있습니다.
배열을 오름차순으로 정렬하기 위해 필요한 최소 교환 횟수를 반환하는 minSwapsToSortLabels 함수를 작성하세요.
제한사항
1 <= labels.length <= 100,000labels[i]는-1,000,000,000이상1,000,000,000이하의 정수입니다.labels의 모든 값은 서로 다릅니다.- 반환값은 배열을 오름차순으로 정렬하는 데 필요한 최소 교환 횟수입니다.
예시
- 입력:
labels = [4, 3, 2, 1]→ 출력:2 - 입력:
labels = [10, -1, 7, 3]→ 출력:2 - 입력:
labels = [1, 2, 3, 4]→ 출력:0 - 입력:
labels = [2, 8, 5, 4]→ 출력:1
힌트
- 각 값이 정렬 후 어디로 가야 하는지 먼저 알아내면 좋습니다.
- 제자리에 있지 않은 원소들을 따라가면 원형으로 이어지는 묶음이 생깁니다.
- 길이가
L인 묶음은 최소L - 1번의 교환으로 정리할 수 있습니다.
해설
이 문제의 핵심은 직접 교환을 시뮬레이션하는 대신, 현재 배열이 만드는 위치 이동 관계를 사이클로 보는 것입니다.
예를 들어 labels = [4, 3, 2, 1]이라면 정렬 결과는 [1, 2, 3, 4]입니다.
- 현재 4는 마지막 위치로 가야 합니다.
- 현재 1은 첫 위치로 가야 합니다.
- 현재 3과 2도 서로 자리를 바꿔야 합니다.
이처럼 각 원소가 이동해야 할 목적지를 따라가면 여러 개의 사이클이 생깁니다.
왜 사이클 길이에서 1을 빼면 될까?
길이가 L인 사이클은 그 안의 원소들이 서로 자리만 바꾸면 해결됩니다.
이때 한 원소를 기준으로 나머지를 제자리로 보내면 최소 교환 횟수는 항상 L - 1번입니다.
예를 들어 길이 3 사이클은:
- 첫 교환으로 한 원소를 제자리로 보내고
- 두 번째 교환으로 나머지 둘도 정리할 수 있습니다.
풀이 순서
labels를 정렬한 배열을 하나 만듭니다.- 각 값이 정렬 배열에서 몇 번째 인덱스에 있어야 하는지 맵으로 저장합니다.
- 원본 배열을 순회하면서 아직 방문하지 않았고 제자리에 있지 않은 인덱스에서 사이클 탐색을 시작합니다.
- 현재 값이 가야 할 다음 인덱스로 이동하며 사이클 길이를 셉니다.
- 사이클 길이가
L이면 답에L - 1을 더합니다. - 모든 인덱스를 처리하면 누적한 값이 최소 교환 횟수입니다.
예시로 보기
labels = [10, -1, 7, 3]
정렬 결과는 [-1, 3, 7, 10]입니다.
현재 인덱스 기준 목적지는 다음과 같습니다.
10은 인덱스3으로3은 인덱스1로-1은 인덱스0으로
즉 0 -> 3 -> 1 -> 0 형태의 길이 3 사이클이 만들어지고, 여기에 필요한 교환 횟수는 2번입니다.
7은 이미 제자리에 있으므로 추가 교환은 필요 없습니다.
이 방식은 정렬에 O(n log n), 사이클 탐색에 O(n)이 들어 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 위치 맵과 방문 배열 때문에 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.