[BOJ] 24060번 : 병합 정렬1

백준 24060번 : 병합 정렬1

🔗 문제 링크

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

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

 

---

🎯 풀이를 위한 개념 설명

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

쉽게 설명을 하자면, 병합 정렬은 입력된 배열을 크기가 1인 부분 배열로 쪼갠 다음, 각 부분 배열의 인덱스 0번째 값을 비교하여 작은 값부터 빈 배열에 넣어 정렬하는 알고리즘이다.

 

병합 정렬에 대해 더 자세한 설명은 아래 글을 참고하길 바란다.

 

https://valueengine.tistory.com/9

[알고리즘] 병합 정렬 (merge sort)

 

---

💬 문제

병합 정렬에 대해 이해를 한 후 문제를 살펴보자

 

1. 첫 번째 줄에 배열의 크기 N과 저장횟수 K가 주어지고, 그 다음줄에 배열 A가 주어진다.

2. 빈 배열 result를 만들고, 병합 정렬 알고리즘에 따라 두 요소를 비교해 result에 추가해준다.

3. 이 때 각 요소가 추가될 때마다 저장 횟수 count가 증가하고, count의 값이 K와 동일하면, 그때 추가된 요소 값을 출력해준다.

4. 만약 K의 값이 저장 횟수보다 크다면, 현실에서 존재할 수 없는 저장 횟수이기에 -1을 출력해준다.

 

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N과 K를 주고, 그 다음줄에 N개의 정수가 주어졌다.

줄바꿈과 공백으로 잘라주고 각 수를 정수화한 뒤, N과 K, 그리고 N개의 수가 들어있는 배열 arr로 할당해주면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이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()로 기존 배열에서 요소를 잘라내 빈 배열에 할당해줄때마다 인덱스의 값이 달라진다. 이 때문에 시간 복잡도가 커진 것으로 보인다.

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

 

🔑 풀이2

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. left에 [4], right에 [5]가 주어지고, 빈 배열 result에 더 작은 수인 4가 입력되고(count 1), 5가 추가된다(count 2)
    [4, 5], [1], [3], [2]
3. left에 [4, 5], right에 [1]이 주어지고, 빈 배열 result에 더 작은 수인 1가 입력되고(count 3), 4와 5가 추가된다(count 5)
    [1, 4, 5], [3], [2]
4. left에 [3], right에 [2]가 주어지고, 빈 배열 result에 더 작은 수인 2가 입력되고(count 6), 3이 추가된다(count 7)
    [1, 4, 5], [2, 3]
5. left에 [1, 4, 5], right에 [2, 3]이 주어지고, 빈 배열 result에 총 5개의 요소가 추가되므로 최종 count는 12가 된다
    [1, 2, 3, 4, 5]

 

left와 right, 그리고 count의 값이 어떻게 변하는지 알고 싶다면 아래의 코드를 참고하면 된다.

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

 

---

References

 

• https://velog.io/@2pandi/Node.js백준-24060-알고리즘-수업-병합-정렬-1