[leetcode] Replace Elements with Greatest Element on Right Side

Description

---

정수 배열이 주어졌을때, 특정 인덱스를 순회하여 자신보다 큰 값이 나오면 특정 인덱스부터 큰 값의 인덱스 사이의 값들을 모두 큰 값으로 바꿔주는 문제. 단, 마지막 원소는 항상 -1 값을 넣어주어야 한다. 

 

 

Input: arr = [17, 18, 5, 4, 6, 1]

Output: [18, 6, 6, 6, 1, -1]

 

Input: arr = [400]

Output: [-1]

 

 

 

 

Success

---

배열 뒤에서 부터 순회하며 현재 값이 앞에 있는 값들보다 큰 경우 모두 현재 값으로 바꿔준다. 

배열 원소가 하나남았을때 다시 반대로 순회하며 배열을 한칸씩 앞으로 채워 -1 값이 들어갈 자리를 만들어준다. 

class Solution {
    public int[] replaceElements(int[] arr) {
        if(arr == null || arr.length == 1) {
            return new int[]{-1};
        }
        
        for(int i=arr.length-1; i>=1; i--) {
            if(arr[i] > arr[i-1]) {
                arr[i-1] = arr[i];
            }
            if (i == 1) {
                for(int j=1; j<arr.length; j++) {
                   arr[j-1] = arr[j];
                   if (j == arr.length-1) {
                       arr[j] = -1;
                   }
                }
            }
        }

        return arr;
    }
}

 

 

 

 

Leetcode Solution

---

위 방법은 완전 비효율적이였다. 아래와 같이 배열 마지막 값을 max 값으로 초기화한 후 -1 값으로 세팅주고 뒤에서 두번째 인덱스부터 배열을 순회하며 max 값을 계속해서 넣어주는 방법으로하면 시간복잡도를 훨씬 단축시킬 수 있다.

class Solution {
    public int[] replaceElements(int[] arr) {
        int n=arr.length-1;
        int max=arr[n];
        arr[n] = -1;
        for(int i=n-1;i>=0;i--){
            int curr = arr[i];
            arr[i] = max;
            if(max<curr) max=curr;
        }
        return arr;
    }
}

 

 

 

출처

---

 

Explore - LeetCode