문제
다음의 값이 주어졌을 때
l = [10, 20, 25, 27, 34, 35, 39]n번 순회를 결정합니다. 예를 들어 2번 순회하면
l = [35, 39, 10, 20, 25, 27, 34]여기서 변하기 전 원소와 변한 후 원소의 값의 차가 가장 작은 값을 출력하는 프로그램을 작성하세요.
예를 들어 2번 순회했을 때 변하기 전의 리스트와 변한 후의 리스트의 값은 아래와 같습니다.
순회 전 리스트 = [10, 20, 25, 27, 34, 35, 39]
순회 후 리스트 = [35, 39, 10, 20, 25, 27, 34]
리스트의 차 = [25, 19, 15, 7, 9, 8, 5]
39와 변한 후의 34 값의 차가 5이므로 리스트의 차 중 최솟값입니다. 따라서 39와 34의 인덱스인 6과 39와 34를 출력하는 프로그램을 만들어주세요.
입력
순회횟수는 : 2
출력
index : 6
value : 39, 34
입력
순회횟수는 : 3
출력
index : 5
value : 35, 25풀이
l = [1, 2, 3, 4, 5], n = 2인 경우를 가정해서 풀이해보겠다.
배열의 맨 뒤 요소를 맨 앞으로 옮기는 과정을 n번 반복한다.
n이 5 이상이면 n % 5만큼 옮겨도 같은 결과가 나온다.
| n회차 | 배열 |
|---|---|
| 0 | 1 2 3 4 5 |
| 1 | 5 1 2 3 4 |
| 2 | 4 5 1 2 3 |
그 뒤, 순회하기 전의 배열과 후의 배열의 차를 구해서
그 차가 제일 작은 요소의 index와
각 배열에서 해당 index에 위치한 값 두개를 뽑아내면 문제는 해결된다.
| 원본 배열 | 1 2 3 4 5 |
| 순회 배열 | 4 5 1 2 3 |
| 차 | 3 3 2 2 2 |
이 때, 배열을 순회하는 방법으로 세가지 정도가 떠올랐다.
1. pop, unshift
배열의 맨 뒤 요소를 맨 앞 요소로 넣어주는 작업이므로 pop()과 unshift()를 사용한다.
for (let i = 0; i < rotatingCount; i++) {
const lastElement = rotatedArray.pop();
rotatedArray.unshift(lastElement);
}2. pop, 재할당
unshift()는 배열의 앞에 요소를 추가하고 나머지 요소들을 하나씩 뒤로 밀어야 해서 성능이 좋지 않다. 그래서 pop()까지만 하고 요소를 앞에 추가하는 작업은 배열을 만들어서 기존 변수에 재할당하는 방법을 생각해봤다.
for (let i = 0; i < rotatingCount; i++) {
const lastElement = rotatedArray.pop();
rotatedArray = [lastElement, ...rotatedArray];
}3. slice, reverse, splice, push
배열의 마지막 요소를 맨 앞에 추가하는 건 결국 마지막 요소를 제거한 배열을 역순으로 정렬해서 뒤에 붙이고 다시 역순으로 정렬하는 것이다.
1 2 3 4 5 => 1 2 3 4 5 => 4 3 2 1 5 => 5 1 2 3 4
마지막 요소 하나만 옮길 때는 위 과정대로 하면 되지만 뒤에서부터 두 개의 요소를 옮길 땐 옮기는 요소들도 역순으로 정렬하는 과정을 거쳐야 한다.
1 2 3 4 5 => 1 2 3 4 5 => 3 2 1 5 4 => 4 5 1 2 3
이 과정을 코드로 적으면 이렇게 된다.
const lastElements = rotatedArray
.slice(arrayLength - rotatingCount)
.reverse();
rotatedArray
.splice(arrayLength - rotatingCount)
.reverse()
.push(...lastElements)
.reverse();위 세가지 방법 중 어떤 방법이 제일 빠른지 JSBEN.CH에서 테스트를 돌려봤다.
배열의 길이는 10000 순회는 9000번으로 테스트했는데 아래의 결과가 나왔다.
vscode에 직접 console.time을 찍어 확인해본 결과도 아래와 같다.
| pop, reassign | pop, unshift | slice, reverse, splice, push | |
|---|---|---|---|
| 1회차 | 394.249ms | 15.674ms | 0.177ms |
| 2회차 | 378.641ms | 15.912ms | 0.193ms |
| 3회차 | 404.125ms | 15.956ms | 0.193ms |
| 4회차 | 400.903ms | 16.476ms | 0.191ms |
| 5회차 | 400.235ms | 15.931ms | 0.191ms |
새로운 배열을 계속 생성해서 할당하는 것보단 기존 배열의 앞에 요소를 추가하는 게 빠르고,
앞에 요소를 추가하는 것보단 기존 배열을 역순으로 돌리는 게 빠른 것 같다.
결과적으로 위 풀이 과정을 코드로 작성하면 아래와 같다.
/**
* 배열을 n만큼 순회한 뒤 원본 배열과의 차가 제일 작은 수의 index와 그 값들을 반환하는 함수
* @param {Array<number>} array 숫자들의 배열
* @param {number} n 순회할 횟수
* @returns 순회 전과 후의 차가 제일 작은 수의 index와 그 값들
*/
function getIndexAndValues(array, n) {
// array.length를 자주 사용하므로 변수로 할당해놓는다.
const arrayLength = array.length;
// 인자로 받은 배열을 원본 배열로 지정한다.
const originArray = array;
// 순회 대상 배열에 원본 배열을 복사한 배열을 할당해놓는다.
let rotatedArray = [...array];
// 순회횟수가 배열의 길이를 넘어가면 넘어간 만큼은 순회할 필요가 없다.
let rotatingCount = n % arrayLength;
// 순회 대상 배열의 뒤에서부터 순회횟수만큼 숫자를 빼서 역순으로 만든다.
const lastElements = rotatedArray
.slice(arrayLength - rotatingCount)
.reverse();
// 순회 대상 배열에서 앞으로 보낼 숫자를 제거하고,
// 역순으로 정렬한 뒤 앞으로 보낼 숫자를 붙이고
// 다시 역순으로 정렬한다.
rotatedArray
.splice(arrayLength - rotatingCount)
.reverse()
.push(...lastElements)
.reverse();
// 원본 배열과 순회할 배열의 차(절댓값)으로 배열을 만든다.
const diffs = originArray.map((element, i) =>
Math.abs(element - rotatedArray[i])
);
// 두 배열의 차 중 최솟값을 구한다.
const smallestDiff = Math.min(...diffs);
// 최솟값의 index를 구한다.
const index = diffs.findIndex((diff) => diff === smallestDiff);
return { index, value: [originArray[index], rotatedArray[index]] };
}
const l = [...new Array(10000)].map((_, i) => i + 1);
const n = 9000;
const { index, value } = getIndexAndValues(l, n);
console.log(`index: ${index}
value: ${value}`);