[BOJ]24060 - 병합 정렬1(JS)

 

풀이

const input = require('fs').readFileSync('예제.txt')
  .toString().trim().split('\n').map((v) => v.split(" ").map((v) => +v));

  //N은 배열의 길이 , K는 찾으려는 K번째 비교에서 추가된 값
const [[N, K], arr] = input;
console.log(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);

 

사실 문제조차도 잘 이해가 가지않아 다른분의 풀이를 참고 할 수 밖에 없었다.

 

처음부터 천천히 코드를 풀이해보자

 

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);
}

-> 

만약 배열의 길이가 1이라면 그대로 그 배열을 리턴한다.

배열의 길이를 반으로 나누고 left에 arr의 0부터 mid 까지 할당한다.(right 또한 마찬가지)

 

merge 함수에 left 와 right를 넣는다.

 

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

-> 빈 배열을 result로 할당

 

i 와 j는 각각 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가 같다면, 마지막으로 추가해준 값 출력
    }
  }

i와 j가 left의 길이 , right의 길이보다 작은동안에

left배열의 i번째 인덱스가 right 배열[j] 보다 작거나같다면

result배열에 left[i] 번째 요소를 추가하고 i 를 증가시킨다 그게아니라면 오른쪽 배열의 j번째 요소를 추가하고 j를 증가시킨다.

count는 증가하며 만약 K가 카운트와 같아진다면 target을 찾았으므로 바로 출력해준다(result의 마지막값)

 

 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;

}

남아있는 값들을 추가한다.

 

작동방식

Initial array: 4,5,1,3,2
Dividing array: 4,5,1,3,2 into left: 4,5,1 and right: 3,2
Dividing array: 4,5,1 into left: 4,5 and right: 1
Dividing array: 4,5 into left: 4 and right: 5
Base case reached with array: 4
Base case reached with array: 5

Merging left: 4 and right: 5
Count: 1, Merged array so far: 4
Count: 2, Adding remaining right elements: 4,5
Merged result: 4,5
Base case reached with array: 1

Merging left: 4,5 and right: 1
Count: 3, Merged array so far: 1
Count: 4, Adding remaining left elements: 1,4
Count: 5, Adding remaining left elements: 1,4,5
Merged result: 1,4,5
Dividing array: 3,2 into left: 3 and right: 2
Base case reached with array: 3
Base case reached with array: 2

Merging left: 3 and right: 2
Count: 6, Merged array so far: 2
Count: 7, Adding remaining left elements: 2,3
Found target at K=7: 3
Merged result: 2,3

Merging left: 1,4,5 and right: 2,3
Count: 8, Merged array so far: 1
Count: 9, Merged array so far: 1,2
Count: 10, Merged array so far: 1,2,3
Count: 11, Adding remaining left elements: 1,2,3,4
Count: 12, Adding remaining left elements: 1,2,3,4,5
Merged result: 1,2,3,4,5
Final target: 3

 

 

배열을 쪼갤 수 있는 단위만큼 쪼개서 정렬하는 방식... 어렵다 정말