Maximum Distance in Arrays

Maximum Distance in Arrays

Account Login - LeetCode

- 문제 내용 : 주어진 숫자 (오름차순 정렬된)Array의 집합에서 가장 작은 값과 가장 큰 값의 차를 구하라. 단, 하나의 Array에서 하나의 숫자만 선택해야 한다.

 

- 접근 방법

• full Search
• Priority Queue (MAX Heap, MIN Heap)
• One Pass

접근은 3가지 방식이 가능한다, 가장 처음 생각하기 좋은 방식은 full search이다. 모든 Array에서 가장 작은 값과 모든 Array에서 가장 큰값을 비교 하는 방식이다.

코드는 다음과 같다.

var maxDistance = function(arrays) {
    let dp = new Array(arrays.length);
    let maxDistance = -10000;

    for(let i = 0; i < arrays.length; i++){ // min
        for(let j = 0; j < arrays.length; j++){ //max
            if(i == j) continue;
            maxDistance = Math.max(maxDistance, arrays[j][arrays[j].length-1] - arrays[i][0]);
        }
    }
    
    return maxDistance;
};

Arrays의 길이가 N이라고 하면 N회 반복함으로써 비교 하면 된다. N회 * N회 반복임으로 N^2이 시간 복잡도 이다.

이 코드로도 문제를 Pass 가능하지만 굉장히 효율성이 떨어진다.

그래서 Priority Queue로 이 효율성을 증가 시켜 줄 수 있다.

class PriorityQ {
    constructor(asc = true) {
        this.arr = new Array();
        this.arr.push('');
        this.asc = asc;
    }

    _compare(a, b){
        if (this.asc) {
            return a < b;
        } else {
            return a > b;
        }
    }

    _compareEq(a, b){
        if (this.asc) {
            return a <= b;
        } else {
            return a >= b;
        }
    }

    push(cost, elem) {
        this.arr.push([cost, elem]);
        let curPosition = this.arr.length-1;

        while (1 < curPosition && this._compare(this.arr[curPosition][0], this.arr[Math.floor(curPosition / 2)][0]) ) {
            let tmp = this.arr[Math.floor(curPosition / 2)];
            this.arr[Math.floor(curPosition / 2)] = this.arr[curPosition];
            this.arr[curPosition] = tmp;
            curPosition = Math.floor(curPosition / 2);
        }
    }

    pop(){
        if(this.arr.length <= 1) return null;
        let curPosition = 1;
        let last = this.arr[curPosition];
        if(2 < this.arr.length) this.arr[curPosition] = this.arr.pop();
        else this.arr.pop();

        while (curPosition * 2 < this.arr.length) {
            if (curPosition * 2 + 1 < this.arr.length && this._compareEq(this.arr[curPosition * 2 + 1][0], this.arr[curPosition * 2][0]) && this._compare(this.arr[curPosition * 2 + 1][0],this.arr[curPosition][0])) { //양쪽이 있고 왼쪽이 작을 경우
                let tmp = this.arr[curPosition * 2 + 1];
                this.arr[curPosition * 2 + 1] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2 + 1;
            } else if (this._compare(this.arr[curPosition * 2][0],this.arr[curPosition][0])){
                let tmp = this.arr[curPosition * 2];
                this.arr[curPosition * 2] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2;
            } else {
                break;
            }
        }

        return last;
    }
}


var maxDistance = function(arrays) {
    let dp = new Array(arrays.length);

    let maxQ = new PriorityQ(false);
    let minQ = new PriorityQ(true);

    let maxDistance = -10000;

    for(let i = 0; i < arrays.length; i++){ // min
        maxQ.push(arrays[i][arrays[i].length - 1], i);
        minQ.push(arrays[i][0], i);
    }

    return getMaxDistance();

    function getMaxDistance(){
        let [maxValue, maxIdx] = maxQ.pop();
        let [minValue, minIdx] = minQ.pop();

        if (maxIdx === minIdx) {
            return Math.max(maxValue - minQ.pop()[0], maxQ.pop()[0] - minValue);
        } else {
            return maxValue - minValue;
        }

    }
};

2020/09/14 - [Problem Solving] - Javascript Priority Queue 오름 차순

Javascript Priority Queue 오름 차순

Priority Queue에 대한 설명은 상위 포스트를 확인 하면 된다.

Prioriry Queue를 사용하게 되면 Insert Log N, Pop Log N의 시간 복잡도를 상용하게 된다.

이를 통해서 기존 N^2을 NlogN으로 시간복잡도를 줄일 수 있다.

기본적으로 최대값과 최소값을 Min,Max 큐에 넣고 최대 2회의 비교를 통해 최대 Distance를 찾게 된다.

왜 최대 2회냐면 하나의 Array에서 최소값과 최대값이 존재 하는 경우가 있을 수 있음으로, 최대 최소가 동일 Array에서 나왔을 경우 다음번 최대값 최소값에서 최대 Distance를 얻어오면 되기 때문이다. 

이와 같은 접근 방법을 Priority Queue가 없이 One Pass로 접근 가능하다.

다음은 One Pass가 가능한 코드이다.

function maxDistance(arrays){
    let result = 0;
    let max = arrays[0][arrays[0].length - 1];
    let min = arrays[0][0];

    for (let i = 1; i < arrays.length; i++) {
        result = Math.max(result, max - arrays[i][0], arrays[i][arrays[i].length - 1] - min);
        max = Math.max(max, arrays[i][arrays[i].length - 1]);
        min = Math.min(min, arrays[i][0]);
    }
    return result;
}

기본적인 접근 방법은 Max와 Min을 Tracking 하면서 항상 다음 Array의 최소값 또는 최대값과 비교 하는 방법이다.

Maximum Distance in Arrays

상기의 그림과 같이 이전 Array에서 선택된 Min과 Max를 다음 Array의 Max와 Min과 비교해서 최대 Length를 남기는 방식으로 계산을 하게 되면, 만약 한 Array에 Min과 Max가 다 있다고 해도 이전 Min과 또는 Max와 비교하는 것이 되기 때문에 하나의 Array에서 Max와 Min을 선택해서 계산 하는 것은 피하게 된다.

시간복잡도는 O(N)이 된다.