사이트: HackerRank
난이도: 미디움
분류: Sorting
배열이 주어졌을 때 인접한 요소의 차이가 최소가 되는 형태로 만드려면 swap을 몇번 해야 하는지 반환하는 문제이다. 인접한 요소의 차이가 최소가 되어야 한다는 말로 보아 정렬로 해결해야 하는문제라고 볼 수 있다.
해당 문제를 선택 정렬로 풀려고 시도해 보다가 시간 초과가 발생하는 테스트 케이스들이 있어서 애먹었던 것 같다.
function lilysHomework(arr) {
// Write your code here
let ascArr = [...arr],
descArr = [...arr],
count1 = 0,
count2 = 0;
for (let i = 0; i < arr.length; i++) {
let min = i,
max = i;
for (let j = i + 1; j < arr.length; j++) {
if (ascArr[min] > ascArr[j]) {
min = j;
}
if (descArr[max] < descArr[j]) {
max = j;
}
}
if (ascArr[i] !== ascArr[min]) {
count1++;
[ascArr[i], ascArr[min]] = [ascArr[min], ascArr[i]];
}
if (descArr[i] !== descArr[max]) {
count2++;
[descArr[i], descArr[max]] = [descArr[max], descArr[i]];
}
}
return Math.min(count1, count2);
}
선택 정렬로 연산시 O(n^2)
이 걸리지만 해당 문제는 정렬된 결과가 아니라 swap된 횟수를 반환하는 것이 키 포인트이다. 따라서 map을 통해 변경해야할 index를 기록해 두고 swap 될 때마다 기록된 index를 갱신시켜주기만 하면 된다. 그렇게 하면 O(nlogn)
만큼의 시간 복잡도가 나온다.
function lilysHomework(arr) {
// Write your code here
const arr1 = [...arr],
arr2 = [...arr],
// 오름차순, 내림차순 각각 정렬된 배열을 생성한다.
asc = [...arr].sort((v1, v2) => v1 - v2),
desc = [...arr].sort((v1, v2) => v2 - v1),
// key: value = 배열 값 : 배열 인덱스 형태로 저장할 map이다.
// 오름차순, 내림차순 각각 저장해야 하기 때문에 2개를 생성한다.
map1 = new Map(),
map2 = new Map();
let count1 = 0,
count2 = 0;
// 현재 배열을 기준으로 map을 생성한다.
arr.forEach((e, i) => {
map1.set(e, i);
map2.set(e, i);
});
for (let i = 0; i < arr.length; i ++) {
// 오름차순 처리
if (arr1[i] !== asc[i]) {
const value = arr1[i];
const index = map1.get(asc[i]);
arr1[index] = value;
arr1[i] = asc[i];
// swap 되었다면 map의 index를 갱신시켜주는 것을 잊으면 안된다.
map1.set(asc[i], i);
map1.set(value, index);
count1++;
}
// 내림차순 처리
if(arr2[i] !== desc[i]) {
const value = arr2[i];
const index = map2.get(desc[i]);
arr2[index] = value;
arr2[i] = desc[i];
map2.set(desc[i], i);
map2.set(value, index);
count2++;
}
}
return Math.min(count1, count2);
}
정렬 문제 같은 경우 생각보다 정렬된 결과보다 해당 문제처럼 부가적인 연산의 횟수나 중간 계산값을 반환하는 문제가 많은 것 같다. 그렇기 때문에 정렬된 결과에 매몰되지 않고 중간 결과를 효율적으로 처리하기 위한 방법을 고민해야 될 것 같다.