8. Replace Elements with Greatest Element on Right Side

문제

https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3259/

주어진 배열 arr을 하나씩 탐색하며, 현재 요소의 우측에 있는 가장 큰 요소를 찾아 현재 요소와 바꾸시오.

마지막 인덱스에는 -1을 넣는다.

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

  

내가 해결한 방식(c++)

인덱스 i로 0부터 끝까지 하나씩 탐색, 

인덱스 j로 인덱스 i 다음 숫자부터 끝까지 하나씩 탐색하면서 최대 숫자 찾기.

time complexity : O(n²)로 너무 오래 걸림

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        // i로 마지막 인덱스 앞까지 탐색
        for (int i = 0; i < arr.size() - 1; i++){
        // i 다음 요소를 max로 설정
        int max = arr[i + 1];
        // i 다음 요소를 j로 지정, 마지막 인덱스까지 탐색하며 최대숫자 검색
        for (int j = i + 1; j < arr.size(); j++){
            if (arr[j] >= max){
                // 현재 최대숫자를 max에 할당 
                max = arr[j];
                // i 인덱스에 최대숫자 할당
                arr[i] = arr[j];
            }
        }
    }
    arr[arr.size() - 1] = -1;
    return arr;
    }
};

 

다른 해결 방법(python)

time complexity : O(n)

arr 배열을 끝에서부터 앞으로 iterate.

def replaceElements(self, arr: List[int]) -> List[int]:
    maximum = -1

    for i in range(len(arr) - 1, -1, -1):
        arr[i], maximum = maximum, max(maximum, current)
        # 풀어쓰면 이하 코드와 같음
        # current = arr[i]
        # arr[i] = maximum
        # maximum = max(maximum, current)

    return arr