[HackerRank] Sorting - (Easy)Sorting: Bubble Sort (버블 정렬) javascript 문제 풀이

■ 문제

원본 사이트: https://www.hackerrank.com/challenges/ctci-bubble-sort/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting 

Sorting: Bubble Sort | HackerRank

 

난이도: Easy

최대 스코어: 30

 

● 문제 요약

> 기본 버블 정렬

for (int i = 0; i < n; i++) {
    
    for (int j = 0; j < n - 1; j++) {
        // Swap adjacent elements if they are in decreasing order
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
        }
    }
}

 

• 정수 배열이 주어지면 버블 정렬 알고리즘을 사용하여 오름차순으로 배열을 정렬
• 다음 세 줄을 인쇄
  1. numSwaps: 발생한 스왑 수
  2. firstElement: 정렬된 배열의 첫 번째 요소
  3. lastElement: 정렬된 배열의 마지막 요소

 

예시:

a = [6, 4, 1]

• swap	a
  0	[6,4,1]
  1	[4,6,1]
  2	[4,1,6]
  3	[1,4,6]

==>  Array is sorted in 3 swaps.  
        First Element: 1  
        Last Element: 6 

 

 

■ 문제 풀이

스왑 수와 정렬된 배열이 필요하기 때문에 직접 버블 정렬을 구현해보라는 문제인 것 같다.

버블 정렬을 실행하면서 스왑 수를 카운트해주면 된다.

 

● 완성 코드 - 30 Points (Max)

'use strict';

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 countSwaps function below.
function countSwaps(a) {
    let count = 0;
    for(let maxIndex=a.length; maxIndex>0; maxIndex--){
        for(let i=0; i<maxIndex; i++){
            if(a[i] > a[i+1]){
                [a[i], a[i+1]] = [a[i+1], a[i]];
                count++;
            }
        }
    }
    console.log('Array is sorted in ' + count + ' swaps.');
    console.log('First Element: ' + a[0]);
    console.log('Last Element: ' + a[a.length-1]);
}

function main() {
    const n = parseInt(readLine(), 10);

    const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));

    countSwaps(a);
}

 

■ 결론

이 문제를 풀면서 도움이 된 점은, swap 할 때 [a[i], a[i+1]] = [a[i+1], a[i]] 식으로 하면 tmp 변수를 이용하지 않고도 두 개의 배열의 값을 바꿀 수 있다는 점이다.