[프로그래머스] K번째 수 (JavaScript)
알고리즘 문제풀이 [프로그래머스] K번째 수 (JavaScript)
프로그래머스 Level 1 - K번째수
- 문제 분류:
정렬 - 문제 출처: 프로그래머스 Level 1 - K번째수
- 라벨:
Level 1,JavaScript
문제
commands 배열은 [i, j, k] 형태의 원소를 가지는 2차원 배열이다. 1차원 배열 array에 대해 commands의 모든 각각의 원소를 적용해야 한다.
- array의 i번째부터 j번째까지 자른다.
1번에서 나온 배열을 정렬한다.2번에서 나온 (정렬된) 배열에서 k번째 숫자를 찾는다.- 이렇게 commands를 돌며
3번에서 나온 숫자들을 배열에 담아 최종적으로 리턴한다.
풀이1
- commands 배열을
forEach로 순회하며 아래 과정을 반복한다. slice()함수를 이용해 array를 자른다.- 잘린 배열(
slicing)을sort()로 정렬한다. - 잘린 배열(
slicing)에서 k번째 수를 찾아 정답 배열(answer)에 넣는다.
🏷️ Syntax
Array.prototype.sort()
- 그냥
sort()는 배열의 요소들을 아스키 코드 순서대로 정렬한다.([100, 1, 4, 13,10]을[1, 10, 100, 13,4]으로 정렬한다. -> 원하는 결과X)sort(function(a, b){ return a - b; });와 같이 작성해야 숫자를 오름차순으로 정렬할 수 있다.- 참고: 자바스크립트 정렬 함수, sort()
- 구조 분해 할당(Destructuring Assignment)
- ex)
[a, b] = [10, 20];- 참고: 구조 분해 할당 - MDN
풀이1 코드
function solution(array, commands) {
let answer = [];
commands.forEach((command) => {
const slicing = array.slice(command[0] - 1, command[1]); // array의 i ~ j번째까지 잘라 새로운 배열에 저장
slicing.sort((a, b) => a - b); // 정렬
answer.push(slicing[command[2] - 1]);
});
return answer;
}
- 시간 복잡도: O(n^2) 보다 클 것으로 예상
- 반복문 안에서
sort()실행하므로
- 반복문 안에서
💡
sort()의 시간 복잡도
- 자바스크립트의
sort()메서드가 호출될 때 어떤 정렬 알고리즘을 사용하는지는 JS엔진에 따라 달라질 수 있다고 한다.- Chrome, Firefox의 경우
sort()는O(n log n)의 시간복잡도를 갖는다고 한다.
풀이2
풀이1의 코드를 간단하게 바꿨다.
풀이2 코드
function solution(array, commands) {
return commands.map(
([i, j, k]) => array.slice(i - 1, j).sort((a, b) => a - b)[k - 1]
);
}
- 시간 복잡도: 풀이1과 동일. O(n^2)보다 클 것으로 예상
풀이3
- 정렬 알고리즘 중에서 버블 정렬을 사용해 문제를 풀었다.
- 버블 정렬 개선: 이미 정렬되어 있는 배열의 경우 반복문을 빨리 벗어날 수 있도록 코드를 작성했다.(
exchg변수 관련)
풀이3 코드
function bubbleSort(arr) {
for (let i = 1; i < arr.length; i++) {
let exchg = 0;
for (let j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
exchg++;
}
}
if (!exchg) break;
}
return arr;
}
function solution(array, commands) {
let answer = [];
answer = commands.map(([i, j, k]) => {
const slicing = bubbleSort(array.slice(i - 1, j));
return slicing[k - 1];
});
return answer;
}
- 시간 복잡도: O(n^3)
map반복 안에서 이중 for문이 실행되므로
- 이 풀이의 경우
sort()를 사용했을 때보다 시간이 좀 더 걸리는 것을 알 수 있다.
