Lily's Homework

사이트: HackerRank
난이도: 미디움
분류: Sorting

문제

배열이 주어졌을 때 인접한 요소의 차이가 최소가 되는 형태로 만드려면 swap을 몇번 해야 하는지 반환하는 문제이다. 인접한 요소의 차이가 최소가 되어야 한다는 말로 보아 정렬로 해결해야 하는문제라고 볼 수 있다.

1. 나의 풀이

해당 문제를 선택 정렬로 풀려고 시도해 보다가 시간 초과가 발생하는 테스트 케이스들이 있어서 애먹었던 것 같다.

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);
}

2. 다른사람의 풀이

선택 정렬로 연산시 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);
}

정리

정렬 문제 같은 경우 생각보다 정렬된 결과보다 해당 문제처럼 부가적인 연산의 횟수나 중간 계산값을 반환하는 문제가 많은 것 같다. 그렇기 때문에 정렬된 결과에 매몰되지 않고 중간 결과를 효율적으로 처리하기 위한 방법을 고민해야 될 것 같다.