(BOJ/JS) #24060: 데이터 정렬 병합 1

쉬운 목차

문제가 있는 링크

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

#24060: 알고리즘 수업 – 병합 정렬 1

배열 A의 크기 N(5 ≤ N ≤ 500,000)과 메모리 수 K(1 ≤ K ≤ 108)는 첫 번째 줄에 지정됩니다. 다른 배열 A의 요소 A1, A2, …, AN은 다음 줄에 지정됩니다. (1 ≤ AI ≤ 109)

www.acmicpc.net

솔루션에 대한 개념 설명

이는 병합 정렬에 대한 이해가 있어야만 풀 수 있는 문제입니다.

간단히 말해서 mergesort는 입력 배열을 크기 1의 하위 배열로 나누고 각 하위 배열의 인덱스 값 0을 비교하여 가장 작은 값을 빈 배열로 정렬하는 알고리즘입니다.

병합 정렬에 대한 자세한 설명은 아래 문서를 참조하십시오.

https://valueengine.9

(알고리즘) 병합 정렬

병합 정렬 1. 병합 정렬이란? 병합 정렬은 문제를 두 개의 더 작은 문제로 분리하고 각각을 해결한 다음 결합하여 원래 문제를 해결하는 분할 정복 알고리즘입니다. 젊은 병합

valueengine.tistory.com

문제

이제 병합 정렬을 이해했으므로 문제를 살펴보겠습니다.

1. 배열 N의 크기와 매장 수 K는 첫 번째 줄에 주어지고 배열 A는 다음 줄에 주어집니다.

2. 빈 배열 결과를 만들고 병합 정렬 알고리즘에 따라 두 요소를 비교하고 결과에 추가합니다.

3. 이때, 각 항목이 추가될 때마다 백업 횟수가 증가하며, 해당 횟수의 값이 K가 되면 그때 추가된 항목의 값이 출력됩니다.

4. K의 값이 점포 수보다 크면 실제로 존재할 수 없는 점포 수이므로 -1을 반환한다.

설명

주어진 배열을 크기 1의 하위 배열로 나누고 0번째 인덱스 값을 비교하도록 코드를 작성했습니다.

하지만… 타임 아웃…

// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
  .toString().trim().split('\n').map((v) => v.split(" ").map((v) => +v));

const ((N, K), arr) = input;


const merge = (left, right) => {
  const result = ();

  while (left.length && right.length) {
    if (left(0) <= right(0)) {     // 0번째 요소끼리 비교
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
    count++;
    if (count === K) {
      target = result(result.length - 1);   // count와 K가 같다면, 마지막으로 추가해준 값 출력
    }
  }

  while (left.length) {
    result.push(left.shift());   // left에 남아있는 값을 추가
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }

  while (right.length) {
    result.push(right.shift());  // right에 남아있는 값을 추가
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }
  return result;
}


// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
let count = 0;
let target;

const mergeSort = (arr) => {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

mergeSort(arr);
if (!target) {
  target = -1;
}
console.log(target);

원인 진단

요소가 기존 배열에서 shift()되고 빈 배열에 할당될 때마다 인덱스 값이 변경됩니다. 이것은 시간적 복잡성을 증가시키는 것으로 보인다.

그래서 좀 더 효율적인 방법을 찾아봤습니다.

shift()로 기존 인덱스에 영향을 주지 않고 인덱스 값을 가져오는 방법은 인덱스 번호로 값을 가져오는 것입니다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
  .toString().trim().split('\n').map((v) => v.split(" ").map((v) => +v));

const ((N, K), arr) = input;


function merge(left, right) {
  const result = ();
  let (i, j) = (0, 0);

  while (i < left.length && j < right.length) {
    if (left(i) <= right(j)) {     // left와 right 요소끼리 비교
      result.push(left(i));
      i++;
    } else {
      result.push(right(j));
      j++;
    }
    count++;
    if (count === K) {
      target = result(result.length - 1);   // count와 K가 같다면, 마지막으로 추가해준 값 출력
    }
  }

  while (i < left.length) {
    result.push(left(i));   // left에 남아있는 값을 추가
    i++;
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }

  while (j < right.length) {
    result.push(right(j));  // right에 남아있는 값을 추가
    j++;
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }
  return result;
}


// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
let count = 0;
let target;

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

mergeSort(arr);
if (!target) {
  target = -1;
}
console.log(target);

예제를 사용한 솔루션

예에서 (4, 5, 1, 3, 2)가 주어집니다. 지정된 배열은 다음 프로세스로 정렬됩니다.

1. 먼저 크기가 1인 하위 배열로 나뉩니다.
(4), (5), (1), (3), (2)
2. (4) 왼쪽과 (5) 오른쪽이 주어지면 빈 배열 결과에 더 작은 숫자 4가 입력되고(카운트 1) 5가 더해집니다(카운트 2).
(4, 5), (1), (3), (2)
3. 왼쪽이 (4, 5)이고 오른쪽이 (1)이면 빈 배열 결과에 더 작은 수 1이 입력되고(카운트 3), 4와 5가 더해집니다(카운트 5).
(1, 4, 5), (3), (2)
4. (3) 왼쪽과 (2) 오른쪽이 주어졌을 때 빈 배열 결과에 더 작은 숫자 2가 입력되고(카운트 6) 3이 더해집니다(카운트 7).
(1, 4, 5), (2, 3)
5. 왼쪽에 (1, 4, 5)와 오른쪽에 (2, 3)이 주어지면 빈 배열 결과에 총 5개의 요소가 추가되므로 최종 개수는 12입니다.
(1 2 3 4 5)

왼쪽, 오른쪽, 개수의 값이 어떻게 변하는지 알고 싶다면 다음 코드를 읽어보세요.

// input값 처리
const input = require('fs').readFileSync('example.txt')
  .toString().trim().split('\n').map((v) => v.split(" ").map((v) => +v));

const ((N, K), arr) = input;


function merge(left, right) {
  const result = ();
  let (i, j) = (0, 0);
  console.log(`(${left}), (${right})`)

  while (i < left.length && j < right.length) {
    if (left(i) <= right(j)) {     // left와 right 요소끼리 비교
      result.push(left(i));
      i++;
    } else {
      result.push(right(j));
      j++;
    }
    count++;
    if (count === K) {
      target = result(result.length - 1);   // count와 K가 같다면, 마지막으로 추가해준 값 출력
    }
  }
  console.log(`결과1: ${result}, count: ${count}`);

  while (i < left.length) {   // left에 남아있는 값을 추가
    result.push(left(i));
    i++;
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }
  console.log(`결과2: ${result}, count: ${count}`);

  while (j < right.length) {  // right에 남아있는 값을 추가
    result.push(right(j));
    j++;
    count++;
    if (count === K) {
      target = result(result.length - 1);
    }
  }
  console.log(`결과3: ${result}, count: ${count}`);
  return result;
}


// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
let count = 0;
let target;

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

mergeSort(arr);
if (!target) {
  target = -1;
}
console.log(target);

참조

https://velog.io/@2pandi/Node.jsbaekjun-24060-algorithm-class-merge-sort-1