[HackerRank] Arrays - (Medium)Minimum Swaps 2 (최소 swap 수 찾기) javascript 문제 풀이

■ 문제

원본 사이트: https://www.hackerrank.com/challenges/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays 

Minimum Swaps 2 | HackerRank

 

난이도: Medium

최대 스코어: 40

 

● 문제 요약

• 중복되지 않은 연속된 정수들 [1, 2, 3, ..., n]로 구성된 정렬되지 않음 배열이 제공됨
• 두 요소를 교환할 수 있음 (swap. 스왑)
• 배열을 오름차순으로 정렬하는 데 필요한 최소 스왑 수를 return

 

예시:

arr = [7, 1, 3, 2, 4, 5, 6]

• i	arr	swap (indices)
  0	[7, 1, 3, 2, 4, 5, 6]	swap (0,3)
  1	[2, 1, 3, 7, 4, 5, 6]	swap (0,1)
  2	[1, 2, 3, 7, 4, 5, 6]	swap (3,4)
  3	[1, 2, 3, 4, 7, 5, 6]	swap (4,5)
  4	[1, 2, 3, 4, 5, 7, 6]	swap (5,6)
  5	[1, 2, 3, 4, 5, 6, 7]

==> 정렬하기 위해 총 5 번의 swap이 발생함

 

 

■ 문제 풀이

우선, 1부터 n까지의 숫자가 중복되지 않게 한 번씩은 나오고, 두 요소를 교환하는 것이기 때문에 정렬하기 조금 편리하다.

서로 교환을 해야하므로 i=1부터 돌고, arr[i-1]을 비교해 위치에 맞는 요소인지 체크한다.
배열의 요소는 0부터 시작하므로 arr[i-1]이 i 값이 되는지를 확인해야 한다.

만약 두 값이 다를 경우, 해당 위치에 잘못된 요소가 있는 것이므로 원래 있어야할 요소를 찾아 서로 교환한다.
그리고 카운트 값을 추가해준다.

이런식으로 모든 요소가 제 위치에 있을 수 있도록 for문을 실행하고 나면, 최소 스왑 수가 나온다.

 

● 완성 코드 - 40 Points (Max)

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the minimumSwaps function below.
function minimumSwaps(arr) {
    let cnt = 0;
    for(let i=1; i<arr.length+1; i++){
        if(arr[i-1] != i){
            let idx = arr.findIndex((element) => element == i);
            [arr[i-1], arr[idx]] = [arr[idx], arr[i-1]];
            cnt++;
        }
    }
    return cnt;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

    const res = minimumSwaps(arr);

    ws.write(res + '\n');

    ws.end();
}