Replace Elements with Greatest Element on Right Side (1299)

07 Apr 2020 in Algoirthm

leetcode 1299번 문제 (java)

문제 내용

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.

• Example

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

• 범위

  1 <= arr.length <= 10^4
  1 <= arr[i] <= 10^5
  

내가 푼 풀이

class Solution {

  public int[] replaceElements(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
      int max = -1;
      for (int j = i + 1; j < arr.length; j++) {
        if (max < arr[j]) {
          max = arr[j];
        }
      }
      arr[i] = max;
    }
    arr[arr.length - 1] = -1;

    return arr;
  }
}

우선 제일 먼저 생각난대로 짠거는 for문을 두 번 써서 max 값을 할당하고 비교하며 값을 치환해주는 형식을 했다.

for문을 한 번 써서 가능해보였는데 밑의 방식대로 뒤에서 시작하면 가능했다.

시간복잡도 측면으로 더 나은 풀이

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