[프로그래머스] JavaScript Lv1 - K번째수(42748)

개요

문제 이름: K번째수 (42748)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42748
플랫폼: 프로그래머스
알고리즘 분류: 정렬
소요 시간: 30분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 배열과 정렬, 인덱싱을 다루는 알고리즘 문제입니다. 주어진 배열에서 특정 구간을 잘라내고, 잘라낸 부분을 정렬한 후, 정렬된 배열에서 지정된 인덱스의 값을 찾아내는 것이 목표입니다.

 

문제에서 요구하는 사항을 정리하면 다음과 같습니다.

1. 배열 array와 2차원 배열 commands가 주어집니다.
2. commands의 각 원소는 [i, j, k]로 이루어져 있습니다.
3. array의 i번째부터 j번째까지 자릅니다. (i, j는 1부터 시작)
4. 자른 배열을 정렬합니다.
5. 정렬된 배열의 k번째 숫자를 구합니다. (k는 1부터 시작)
6. 모든 commands에 대해 위 과정을 수행하고, 결과를 배열에 담아 반환합니다.

이러한 문제를 해결하기 위해서는 배열 슬라이싱(slicing), 정렬(sorting), 인덱싱(indexing)을 사용해야 합니다.

• map: 배열의 각 요소에 대해 콜백 함수를 실행하고, 그 결과를 새로운 배열로 반환합니다.
• slice: 배열의 일부분을 선택하여 새로운 배열로 반환합니다. 시작 인덱스는 포함되고, 끝 인덱스는 제외됩니다.
• sort: 배열의 요소를 정렬합니다. 비교 함수를 전달하여 정렬 기준을 지정할 수 있습니다.

이번 문제에 사용된 메서드들은 위와 같습니다.

 

시도

1차 시도  (실패)

// 1차 시도 (실패)
function solution(array, commands) {
	let answer = commands.map((value) => {
		return array.slice(value[0] - 1, value[1]).sort()[value[2] - 1];
	});
	return answer;
}

1차 시도에서는 map과 slice, sort 메서드를 사용하여 문제를 해결하려 했습니다. map 메서드를 사용하여 commands 배열을 순회하면서, 각 command에 대해 slice로 배열을 자르고, sort로 정렬한 후, 지정된 인덱스의 값을 반환했습니다.

하지만 이 코드에서는 sort 메서드를 사용할 때 비교 함수를 전달하지 않았기 때문에, 문자열 기준으로 정렬이 수행됩니다. 따라서 숫자 배열이 올바르게 정렬되지 않아 원하는 결과를 얻을 수 없었습니다.

 

2차 시도  (성공)

// 2차 시도 (성공)
function solution(array, commands) {
	let answer = commands.map((value) => {
		return array.slice(value[0] - 1, value[1]).sort((a, b) => a - b)[value[2] - 1];
	});
	return answer;
}

2차 시도에서는 sort 메서드에 비교 함수를 전달하여 숫자 배열을 올바르게 정렬할 수 있도록 수정했습니다. 비교 함수 (a, b) => a - b는 오름차순으로 정렬하도록 만듭니다.

이제 slice로 잘라낸 배열을 숫자 기준으로 정렬하고, 지정된 인덱스의 값을 반환할 수 있습니다. 이 코드는 정상적으로 동작하며, 모든 테스트 케이스를 통과할 수 있었습니다.

 

3차 시도 (성공)

// 3차 시도 (성공)
function solution(array, commands) {
	let answer = commands.map(([startIndex, endIndex, targetIndex]) => {
		return array.slice(startIndex - 1, endIndex).sort((a, b) => a - b)[targetIndex - 1];
	});
	return answer;
}

3차 시도에서는 배열 구조 분해 할당(destructuring assignment; 구조 분해 할당)을 사용하여 코드를 더욱 간결하게 만들었습니다. map 메서드의 콜백 함수에서 [startIndex, endIndex, targetIndex]와 같이 배열 구조 분해 할당을 사용하여 command의 각 원소를 직관적인 변수명으로 할당했습니다.

이렇게 하면 value[0], value[1], value[2] 대신 의미 있는 변수명을 사용할 수 있어 코드의 가독성이 향상됩니다.

 

4차 시도 (성공)

// 4차 시도 (성공) - 풀어서 보여주기
function solution(array, commands) {
	const answer = commands.map((command) => {
		const [startIndex, endIndex, targetIndex] = command;
		const slicedArray = array.slice(startIndex - 1, endIndex);
		const sortedArray = slicedArray.sort((a, b) => a - b);
		const targetNumber = sortedArray[targetIndex - 1];
		return targetNumber;
	});

	return answer;
}

4차 시도에서는 3차 시도의 코드를 더욱 풀어서 작성했습니다. 각 단계를 변수에 할당하고, 중간 결과를 명시적으로 선언하여 코드의 흐름을 쉽게 이해할 수 있도록 만들었습니다.

1. command에서 startIndex, endIndex, targetIndex를 배열 구조 분해 할당으로 추출합니다.
2. slice 메서드를 사용하여 startIndex부터 endIndex까지 배열을 자릅니다.
3. sort 메서드를 사용하여 잘라낸 배열을 오름차순으로 정렬합니다.
4. 정렬된 배열에서 targetIndex에 해당하는 숫자를 선택합니다.
5. 선택한 숫자를 반환합니다.

해당 4차 코드는 이전 3차 시도와 동일한 결과를 반환하지만, 사실상 이해하기 쉽게 풀어낸 코드입니다. 크게 다른 건 없습니다.

 

시간 복잡도는 O(n log n)입니다. map 메서드의 콜백 함수는 각 command에 대해 한 번씩 실행되므로 O(m)이고, 내부적으로 slice와 sort를 수행하는데, sort의 시간 복잡도가 O(log n)이므로 전체적인 시간 복잡도는 O(m * log n)입니다. 여기서 m은 commands의 길이, n은 array의 길이입니다. 공간 복잡도는 O(n)입니다. slice 메서드를 사용할 때마다 새로운 배열을 생성하므로, 최악의 경우 O(n)만큼의 추가 공간이 필요합니다.

 

사족

이 문제를 통해 배열 메서드의 활용법을 익힐 수 있었습니다. map, slice, sort 등의 메서드를 적절히 조합하여 간결하고 효율적인 코드를 작성할 수 있다는 걸 깨달았습니다. 마지막으로 비교 함수를 사용하여 정렬 기준을 지정하는 방법도 배울 수 있었습니다.