K번째 수

boyeonJ·2023년 5월 7일

알고리즘

목록 보기

7/17

퀵정렬을 이용한 풀이

function solution(array, commands) {
    var answer = [];
    
    for(let i in commands){
        answer.push(getOutput(commands[i], array))
    }
    
    return answer;
}

const getOutput = (input, array) => {
    const sortArray = sort(array.slice(input[0]-1, input[1]));
    return sortArray[input[2]-1];
}

const sort = (array) => {
  if (array.length <= 1) {
    return array;
  }

  const pivot = array[0]
  const leftArr = [];
  const rightArr = [];
    
  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      leftArr.push(array[i]);
    } else {
      rightArr.push(array[i]);
    }
  }
    
  return sort(leftArr).concat(pivot, sort(rightArr));
}

더 간결하고 가독성 있게 작성

구조분해할당 sort

function solution(array, commands) {
    const answer = [];
    
    for(const command of commands){
        const [start, end, k] = command;
        const sortedArray = array.slice(start-1, end).sort((a, b) => a - b);
        answer.push(sortedArray[k-1])
    }
    
    return answer;
}

회고하기

1. for-in과 for-of

for-in 루프는 배열의 인덱스뿐만 아니라, 해당 객체의 모든 프로퍼티를 순회하므로, 배열을 순회할 때는 for-in 루프보다 for-of 루프를 사용하는 것이 좋습니다. for-of 루프는 배열의 요소를 순회하는 것이 목적이기 때문에 더 간결하고 직관적입니다.

2. 퀵정렬과 sort 매서드

자바스크립트에서는 Array.prototype.sort() 메서드가 내부적으로 퀵정렬, 삽입정렬, 병합정렬 등을 사용하여 정렬을 수행합니다. 이때 정렬 알고리즘은 입력 데이터의 크기, 형태, 브라우저 등에 따라 자동으로 선택됩니다. 따라서 개발자는 알고리즘의 세부적인 내용보다는 Array.prototype.sort() 메서드의 사용 방법과 주의점을 잘 이해하는 것이 중요합니다.

문제 상황이나 환경에 따라서는 Array.prototype.sort() 메서드보다 다른 정렬 알고리즘이 더욱 적합할 수 있습니다. 예를 들어, 배열의 요소가 매우 큰 객체이거나 비교 함수의 연산이 복잡한 경우에는 다른 정렬 알고리즘을 고려해볼 필요가 있습니다.