[BOJ] 11004번 : K번째 수

백준 11004번 : K번째 수

🔗 문제 링크

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

11004번: K번째 수

 

---

💬 문제

 정렬 알고리즘 에 대한 이해가 있다면, 충분히 이해할 수 있는 문제다.

다만, 시간 초과와 메모리 초과 때문에 조금 어렵게 다가올 수 있다.

 

1. 첫 번째 줄에 정수 개수 N과 인덱스번호 K가 주어지고, 두 번째 줄에 공백으로 N개의 정수가 주어진다.
   
   
2. N개의 정수를 오름차순으로 정렬했을 때, K번째 수를 출력해준다.
   
   

 

---

💡 입력값 받아오기

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

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

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

 

 

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

https://valueengine.tistory.com/2

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

 

728x90

 

---

💻 풀이

이 문제는 여러가지 정렬 알고리즘으로 풀 수 있다.

총 3가지 방식으로 풀어볼 것이다.

 

🔑 풀이1 : sort() 메서드

• 줄바꿈과 공백을 기준으로 잘라주고, 모든 수들을 정수화해준다.
  
  - 정수 개수 N과 K번째, 배열 arr를 구조분해할당해준다
    
• 배열 arr를 오름차순으로 정렬해주고, K번째 수를 출력해준다.
  
  - 인덱스번호는 0번부터 시작하므로, K번째는 K-1이 된다

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

const [[N, K], arr] = input;

console.log(solution(arr)[K-1]);  // K번째 수

function solution(arr) {
  return arr.sort((a, b) => a - b);  // 오름차순 정렬
}

 

시간은 다음과 같이 걸렸다. 시간 효율은 그렇게 좋지 않았다.

 

 

---

🔑 풀이2 : 병합 정렬

• 줄바꿈과 공백을 기준으로 잘라주고, 모든 수들을 정수화해준다.
  
  - 정수 개수 N과 K번째, 배열 arr를 구조분해할당해준다
    
• 함수 mergreSort()로 크기가 1인 부분 배열로 쪼개주고, 함수 merge()를 통해 각 부분 배열의 요소를 비교해 정렬한다.
    
• 정렬된 배열에서 K번째 수를 출력해준다.

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

const [[N, K], arr] = input;

console.log(mergeSort(arr)[K-1]);  // K번째 수

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++;
    }
  }
  while (i < left.length) {
    result.push(left[i]);   // left에 남아있는 값을 추가
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);  // right에 남아있는 값을 추가
    j++;
  }
  return result;
}

// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

 

병합 정렬로도 풀어봤으나 메모리가 초과되어 실패했다ㅠㅠ

 

 

병합 정렬에 대해 더 알고 싶다면 아래 글을 참고해 공부해보자.

https://valueengine.tistory.com/9

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

 

---

🔑 풀이3 : 퀵 정렬

• 줄바꿈과 공백을 기준으로 잘라주고, 모든 수들을 정수화해준다.
  
  - 정수 개수 N과 K번째, 배열 arr를 구조분해할당해준다
    
• 퀵 정렬 함수인 quickSort()로 pivot 값(기준값)을 정하고, 함수 divide()를 통해 배열의 값들을 비교하여 정렬해준다.
    
• 정렬된 배열에서 K번째 수를 출력해준다.

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

const [[N, K], arr] = input;

console.log(quickSort(arr, 0, arr.length -1)[K-1]);  // K번째 수

function quickSort(arr, left, right) {
  if (left >= right) {
    return;
  }
  // 기준점
  const mid = Math.floor((left + right) / 2);
  const pivot = arr[mid];
  const partition = divide(arr, left, right, pivot);

  quickSort(arr, left, partition - 1);
  quickSort(arr, partition, right);

  return arr;
}

function divide(arr, left, right, pivot) {
  while (left <= right) {
    while (arr[left] < pivot) {  // pivot과 비교
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }

    if (left <= right) {   // 왼쪽 값과 오른쪽 값을 바꾸기
      let tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
      left++;
      right--;
    }
  }
  return left;
}

 

다행히 퀵 정렬로는 메모리나 시간 초과 없이 풀렸다.

 

 

퀵 정렬에 대해선 아래 글을 참고해 공부해보자

https://valueengine.tistory.com/11

[알고리즘] 퀵 정렬 (Quick Sort)