HackerRank 문제풀이 - 7 (Minumum Swaps 2)

1.문제

• 임의의 숫자들을 담은 랜덤 길이의 배열이 주어진다.(숫자들은 중복되지 않는다.)
  • 해당 배열이 1부터 arr.length-1 까지 순차적으로 정렬되게 해야한다.
    • 정렬은 배열 내 항목들을 swap하는 방식으로 이루어진다.
      • 최소한으로 몇번의 swap을 해야 정렬이 완성되는지 구하는 문제이다.

 

2. 문제풀이

2.1 풀이 과정

function minimumSwaps(arr) {
    let swapedNum = 0;
    
    for(let i = 0; i < arr.length; i++){
        const correctNum = i + 1;
        
        if(arr[i] != correctNum){
            for(let j = i; j < arr.length; j++){
                if(arr[j] == correctNum){
                    arr[i] = arr.splice(j, 1, arr[i])[0];
                    console.log(`swaped ${i}<>${j}`);
                    console.log(arr);
                    
                    swapedNum++;
                    break;
                }
            }
        } 
    }
    
    return swapedNum;
}

풀이 방법은 다음과 같다.

• 배열의 길이만큼 for문을 돈다.
  • for문의 증가하는 i값 + 1이 해당 index에 맞는 숫자(correctNum)이라고 정의한다.
    • 만일 해당 인덱스에 맞는 숫자가 있지 않으면, 현재 탐색중인 index부터 마지막 index까지 탐색하여 해당 숫자를 찾는다.
      • 해당 숫자를 찾은 경우, 현재 인덱스와 해당 인덱스끼리 요소를 바꿔준다.
      • 바꾼 횟수(swapedNum)를 1 더한다.
• 마지막까지 반복문을 돌면, 계산된 바꾼 횟수(swapedNum)값을 리턴한다.

 

2.2 풀이 결과

이러하여 모든 테스트 케이스를 통과하였다.

찍은 로그(Debug output)을 확인해봐도, 순차적으로 알맞게 swap이 이루어지는 것을 확인해 볼 수 있다.

 

이렇게 큰 배열도 Test case로 주어졌다니..

해당 Test case도 약 10초가량?의 시간이 흘러 위와같이 정상 연산되었음을 확인할 수 있었다.