[자바스크립트] 24060 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1

문제

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

 

 

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

 

 

출력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

 

 

예제 입력 1

5 7
4 5 1 3 2

 

 

예제 출력 1

3

 

 

자료구조

입력

① N: 정수 배열의 길이

② K: 찾고자 하는 K번째 작은 수 

③ arr: 정수 배열

출력

① target: K번째 작은 수

 

 

알고리즘

병합 함수 (merge):

• 두 개의 정렬된 배열 arr1과 arr2를 병합하여 하나의 정렬된 배열을 만든다.
• 병합 과정에서 원소를 추가할 때마다 count를 증가시키며, count가 K와 같아지면 현재 추가된 원소를 target 변수에 저장한다.

병합 정렬 함수 (mergeSort):

• 배열을 재귀적으로 반으로 나누고, 각 부분 배열을 병합하여 정렬된 배열을 만든다.
• 원소가 1개 이하인 경우 그대로 반환.
• 그렇지 않은 경우, 배열을 중간(소수점 올림)에서 나눠 왼쪽과 오른쪽 부분 배열을 각각 정렬한 후 병합한다.

 

 

소스 코드 1

let fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().split("\n");

const [N, K] = input[0].split(" ").map((v) => +v);
const arr = input[1].split(" ").map((v) => +v);;

let count = 0;
let target = -1;

const checkCount = (results) => {
  if (count === K) {
    target = results[results.length - 1];
  }
};

// 병합 수행(conquer) 함수
const merge = (arr1, arr2) => {
  let results = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      results.push(arr1[i]);
      i++;
    } else {
      results.push(arr2[j]);
      j++;
    }
    count++;
    checkCount(results);
  }

  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
    count++;
    checkCount(results);
  }

  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
    count++;
    checkCount(results);
  }
  return results;
};

// 병합 정렬 함수
const mergeSort = (arr) => {
  if (arr.length <= 1) return arr; // 원소가 1개인 경우, 해당 배열은 정렬이 된 상태
  
  // 원소가 2개 이상
  let mid = Math.ceil(arr.length / 2);     // 분할(divide): 2개의 부분 배열로 분할
  let left = mergeSort(arr.slice(0, mid)); // 수행(conquer): 왼쪽 부분 배열 정렬 수행
  let right = mergeSort(arr.slice(mid));   // 수행(conquer): 오른쪽 부분 배열 정렬 수행
  return merge(left, right);          // 병합(combine): 정렬된 2개의 배열을 하나로 병합
};

mergeSort(arr);
console.log(target);

732ms

다 같이 머리싸매가며 고민한 결과 난 좀 허무했어😂

프론트엔드 코테는 역시 JS!

 

 

빅오(O) 표기법

병합 정렬 (Merge Sort)

① 최악의 경우, 평균의 경우 $O(NlogN)$

 

 

 

✔ 출처

https://www.acmicpc.net/problem/24060