[알고리즘] Leetcode. Replace Elements with Greatest Element on Right Side

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

 

배열 arr가 주어지고 모든 엘리먼트를 오른쪽에 있는 엘리먼트 중 제일 큰 엘리먼트로 바꾸세요. 그리고 마지막 엘리먼트는 -1로 바꾸세요.

마지막으로 배열을 리턴하세요.

 

- 처음 푼 코드

var replaceElements = function(arr) {
    let greatestNumber; 
    
    for (let i = 0; i < arr.length; i++) {
        greatestNumber = arr[i + 1];
        
        for (let j = i + 2; j < arr.length; j++) {
            if (greatestNumber < arr[j]) {
                greatestNumber = arr[j];
            }
        }
        arr[i] = greatestNumber;
    }
    
    arr[arr.length - 1] = -1;
    
    return arr;
};

시간복잡도가 O(n^2) 으로 좋은 코드는 아닌 것 같다.

공간복잡도는 O(1)

 

- 다시 풀기

var replaceElements = function(arr) {
    let greatestNumber = arr[arr.length - 1]; 
    let temp;
    
    for (let i = arr.length - 2; i >= 0; i--) {
        temp = arr[i];
        arr[i] = greatestNumber;

        if (temp > greatestNumber) {
            greatestNumber = temp;
        }
    }

    arr[arr.length - 1] = -1;
    
    return arr;
};

얼핏 보면 두 개의 루프를 이용해야 할 것 같지만 엘리먼트 값의 오른쪽 값을 비교하는 것이기 때문에 for문을 끝에서부터 시작하면 된다. 

 

 

 

 

참고할 사이트

https://www.geeksforgeeks.org/replace-every-element-with-the-greatest-on-right-side/

Replace every element with the greatest element on right side - GeeksforGeeks