백준 - 1517 버블 소트

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 31314 8646 5897 30.188%
문제
N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

입력

• 첫째 줄
  • N
• 둘째 줄부터
  • N개의 정수, A[1], A[2], …, A[N]

제한 조건

• 1 ≤ N ≤ 500,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

예시

// NOTE: 입력
3
3 2 1

// NOTE: 출력
3

해결

아니 진짜
이 문제 버블정렬 아니다
병합정렬이다🥹

메모리 초과 + 시간 초과

• 버블정렬: O(N^2)
• 병합정렬: O(NlogN)

버블 정렬을 쓰면,
최악의 경우(모두 내림차순으로 정렬된 경우)에 500,000의 제곱만큼 반복해야 한다.

그래서 좀 더 효율적인 병합 정렬을 사용해야 한다.

merge 함수에서 시간 초과

• 배열 조작(merge함수에서 shift와 push를 이용) >> 시간 초과
• index를 조작 >> 해결!

역시 배열의 크기가 클 땐,
배열을 직접 조작하는 메소드는 적합하지 않다.
ex. shift, push 등등

이럴 땐, index를 기억하는 변수를 사용하면 훨씬 빠르게 계산할 수 있다.

mergeSort 함수

• list를 반으로 나누는 함수
  • 반으로 slice 하고
  • merge한 list를 return

merge 함수

• list를 병합정렬하여 return 하는 함수
• sortArr 배열 선언
• right, left 리스트의 포인터를 담당할 변수를 선언
  • leftIdx == 0
  • rightIdx == 0
• right나 left 둘 중 하나를 완전탐색할 때까지
  • right[rightIdx] < left[leftIdx] 인 경우,
    • swap이 필요한 경우
    • sortArr에 right[rightIdx] push
    • rightIdx + 1;
    • swap 카운트에 (left의 개수 - sortArr의 개수 + rightIdx)를 더한다.
  • left[leftIdx] >= right[rightIdx]
    • swap이 필요없는 경우
    • sortArr에 leftList[leftIdx] push
    • leftIdx + 1
• sortArr + left.slice(leftIdx) + right.slice(rightIdx)를 return

전체 코드

const [N, inputs] = require('fs')
    .readFileSync('dev/stdin')
    .toString()
    .trim()
    .split('\n');
let _swapCount = 0;

// NOTE: 시간복잡도 O(N^2)인 버블 정렬로 풀면 안됨! >> 병합 정렬 (O(NlogN))
const solution = () => {
    const _inputArr = inputs.split(' ').map(v => +v);
    
    mergeSort(_inputArr);
    console.log(_swapCount);
};

// NOTE: 병합정렬한 list를 return하는 함수
const merge = (leftList, rightList) => {
    const _sortArr = [];
    
    let _leftIdx = 0;
    let _rightIdx = 0;
    
    // NOTE: left와 right 둘 중 하나가 빌 때까지
    while(_leftIdx < leftList.length && _rightIdx < rightList.length) {
        const _isSorted = leftList[_leftIdx] > rightList[_rightIdx];
        
        if (_isSorted) {
            _sortArr.push(rightList[_rightIdx++]);
            _swapCount += leftList.length - _sortArr.length + _rightIdx;
        } else {
            _sortArr.push(leftList[_leftIdx++]);
        }
    }
    
    return [..._sortArr, ...leftList.slice(_leftIdx), ...rightList.slice(_rightIdx)];
};

// NOTE: list를 반갈죽 하는 함수
const mergeSort = (list) => {
    if (list.length == 1) return list;
    
    const _mid = Math.ceil(list.length / 2);
    const _leftList = list.slice(0, _mid);
    const _rightList = list.slice(_mid);
    
    return merge(mergeSort(_leftList), mergeSort(_rightList));
};

solution();

---

백준 1517번: 버블 소트