일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 딥다이브
- 해시
- 합병 정렬
- 코딩테스트
- 백준
- 자바스크립트
- state
- 코테
- 완전탐색
- sort
- 정렬
- 최소공배수
- 알고리즘
- JS
- 기술면접
- 정규표현식
- CSS
- JavaScript
- 브루트포스
- 연결리스트
- Node
- 프로그래머스
- BOJ
- hash
- 자료구조
- 리액트
- 병합 정렬
- node.js
- useState
- react
- Today
- Total
가치투자자
[BOJ] 11004번 : K번째 수 본문
백준 11004번 : K번째 수
🔗 문제 링크
https://www.acmicpc.net/problem/11004
11004번: K번째 수
수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
💬 문제
정렬 알고리즘 에 대한 이해가 있다면, 충분히 이해할 수 있는 문제다.
다만, 시간 초과와 메모리 초과 때문에 조금 어렵게 다가올 수 있다.
- 첫 번째 줄에 정수 개수 N과 인덱스번호 K가 주어지고, 두 번째 줄에 공백으로 N개의 정수가 주어진다.
- N개의 정수를 오름차순으로 정렬했을 때, K번째 수를 출력해준다.
💡 입력값 받아오기
JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.
이 문제에서는 1번째 줄에 N과 K를 주고, 그 다음줄에 N개의 정수가 주어졌다.
줄바꿈과 공백으로 잘라주고 각 수를 정수화한 뒤, N과 K, 그리고 N개의 수가 들어있는 배열 arr로 할당해주면 된다.
입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.
https://valueengine.tistory.com/2
[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅
1. Node.js fs모듈 사용법 백준에서 JavaScript로 문제를 풀기 위해선 Node.js를 사용해야 하며, 이때 readline 모듈이나 fs 모듈로 입력값(input)을 받아와야 한다. 이 중 속도나 코드의 길이, 작성 편리성에
valueengine.tistory.com
💻 풀이
이 문제는 여러가지 정렬 알고리즘으로 풀 수 있다.
총 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)
병합 정렬 (merge sort) 1. 병합 정렬이란? 병합 정렬(merge sort)은 어떤 문제를 2개의 작은 문제로 분리해 각각 해결한 다음, 이걸 모아서 원래 문제를 해결하는 분할 정복 알고리즘 중 하나다. 병합 정
valueengine.tistory.com
🔑 풀이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)
퀵 정렬 (Quick Sort) 1. 퀵 정렬이란? 퀵 정렬(quick sort) 역시 병합 정렬과 마찬가지로 어떤 문제를 2개의 작은 문제로 분리해 각각을 해결하는 분할 정복 알고리즘 중 하나다. 1-1) 차이점 병합 정렬 -
valueengine.tistory.com
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 9506번 : 약수들의 합 (0) | 2023.04.06 |
---|---|
[BOJ] 2501번 : 약수 구하기 (0) | 2023.04.06 |
[BOJ] 11650번 : 좌표 정렬하기 (0) | 2023.04.04 |
[BOJ] 10814번 : 나이순 정렬 (0) | 2023.04.02 |
[BOJ] 1427번 : 소트인사이드 (0) | 2023.03.31 |