[Array] 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.

 

문제 자체는 간단하다.

특정 element에 대해, 그 오른쪽에 있는 원소들의 크기를 가늠한 후, 가장 크기가 큰 원소의 값으로 대체하는 것.

 

이러한 문제는 사실 배열을 다룰 때, 공간복잡도를 최소화하기 위한 예시로 많이 쓰인다.

흔히 In-place Array Operation이라 한다.

새로운 배열을 만들어 조건대로 원소를 꾸리면 좋겠지만, 이는 메모리 할당으로 인해 쓸데없이 리소스가 소모된다. 

따라서 기존 배열에 대해 Overwrite하는 방식으로 배열을 처리해주는 것이 In-place Array Operation이다.

 

문제 해결 방법은 다음과 같다

 

1) 배열 Loop를 돌되, 배열의 변질을 예방(?)하기 위해 뒤부터 돈다

 

2) 인덱스는 o와 n 두개를 둔다.

o는 특정원소 오른쪽에 있는 원소들 중 최대값을

n은 그 다음 최대값을 의미한다

이때 문제의 조건대로 처음 Loop를 도는 시점에서 o는 -1이 될 것이다.

 

3) Loop를 돌면서 현재원소와 이전원소의 최대값을 비교한다

이때 현재원소는 o로 대체하고, o는 다시 n으로 대체하여 그 다음 원소의 최대값을 배정한다

 

 

var replaceElements = function(arr) {

    let o = -1;

  let n = 0;

  for (let i = arr.length-1; i >= 0; i--) {

      n = Math.max(arr[i], o);

      arr[i] = o;

      o = n;

  }

  return arr;

};