[LeetCode] 1299. Replace Elements with Greatest Element on Right Side

1299. Replace Elements with Greatest Element on Right Side

Easy

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 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation: 
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

 

Constraints:

• 1 <= arr.length <= 104
• 1 <= arr[i] <= 105

---

문제 풀이

주어진 숫자 배열에서 현재 인덱스보다 오른쪽에 있는 값들 중에 최대값을 저장하는 문제이다.

맨 마지막 숫자는 무조건 -1을 답으로 넣어야한다.

Max: Time Limitation Error

• 현재 위치 외의 오른쪽 숫자들 중에 최대값을 찾아야한다.
• 만약 왼쪽에서 부터 답을 찾아가는 방법으로도 답을 구할 수 있지만, 현재 위치를 제외하고 매번 (N - i - 1)만큼의 탐색을 해야한다.
• i + 1 ~ N까지의 숫자들 중에 하나의 가장 큰 숫자를 구해야하기 때문이다.
• 즉 최종 시간복잡도는 O(N!)이 되기 때문에 문제 제한사항인 N^4에도 맞게 풀릴 수 가 없다.
• 결국 시간초과 에러가 발생한다.

Swap & max

• 이를 간단하게 풀기 위해서는 하나의 방법을 사용한다.
• 현재 위치에서 오른쪽의 모든 숫자들을 확인해야한다.
• 하지만 반대로 생각하면 오른쪽 부터 큰 숫자를 찾아 진행하면 매번 현재 위치 오른쪽의 모든 값을 비교할 필요가 없다.
• 다시말해 맨 오른쪽의 값이 현재의 최대값이라고 정하고 왼쪽으로 옮기면서 숫자를 비교해본다면 오른쪽 끝자리부터 최대값은 항상 보장이 된다. 
• 예를 들어, 1, 2, 3이 있다면 맨 마지막 숫자를 최대값으로 정하고 index 2 위치에 저장한다.
• 그리고 index 1로 갔을때 최대값으로 저장되어 있는 숫자는 오른쪽에서 왼쪽으로 한 자리씩 거쳐오면서 저장되는 최대값이다.
• 즉 index 1에서 얻는 최대값은 3이며, index 0으로 이동했을때도 최대값은 3이다.
• 그리고 마지막 값에 -1를 넣어주기 위해서 처음 최대값 변수의 값은 -1로 정한다.
• 맨 오른쪽 값부터 최대값을 갱신하면서 왼쪽으로 이동한다. 
• 이때 최대값을 구하기 전에 temp에 넣어놨던 값을 arr 배열 현재 위치에 넣고 temp에는 현재 위치와 temp중에 최대값을 넣는다.
• 즉 현재 위치와 지금까지 최대값이였던 임시 변수와 크기 비교를 하여 temp에 넣고 이전에 가지고 있던 temp 즉 오른쪽의 최대값은 배열 현재 위치에 넣어준다. 
• 다시말해 오른쪽에서 시작해서 이전 최대값은 temp 변수에 저장해놓았다가 매번 갱신하기전에 이전 최대값을 현재 위치에 저장해야 한다.

Sort

• 배열의 값과 인덱스를 튜플로 묶어 역순으로 정렬하는데 내림차순으로 정렬하는 거라고 봐도 무방한다. 
• 인덱스를 같이 저장하여 정렬하면서, 최대값을 비교할때 그 최대값이 현재 인덱스보다 크다면 정답으로 가질 수 있도록 하였다.
• 즉 포인터를 두개 이용하여 값과 인덱스가 내림차순으로 정렬되어있는 배열을 탐색한다. 
• 하나의 포인터는 항상 현재 위치를 나타내고, 두번째 포인터는 최대값부터 작은 값을 향해 나아간다.
• 현재 위치에서 그 인덱스를 이용하여 내림차순으로 정렬되어있는 값을 확인한다.
• 내림차순으로 정렬되어있기 때문에 오른쪽으로 갈수록 작아진다. 
• 확인하는 방법은 단순히 인덱스만 비교하면서 포인터를 정렬된 배열 끝까지 while문으로 탐색한다.
• 숫자가 점점 작아지면서 현재 인덱스보다 크면 이동을 멈춘다. 
• 이는 현재 위치보다 큰 인덱스일 경우 가장 큰 값을 찾는 논리이다.
• 즉 정렬된 배열안에서 항상 맨 왼쪽에 있는 숫자들은 크다는 것이 보장되어있고 현재 인덱스가 저장되어있는 인덱스보다 작다는 것은 그 숫자는 현재 위치의 오른쪽에서 가장 큰 값을 나타낸다.
• 그리고 정답 배열 마지막에 -1를 넣어준다.

소스 코드

Max: Time Limitation Error

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        # max O(n!) TLE
        ans = [0] * len(arr)
        for i in range(len(arr) - 1):
            ans[i] = max(arr[i+1:])
        ans[-1] = -1
        return ans

Swap & max

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
    # swap & max O(N)
        temp = -1
        for i in range(len(arr) - 1, -1, -1):
            arr[i], temp = temp, max(temp, arr[i])
        return arr

Sort

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        # sort O(nLogn)
        arr = [(num, i) for i, num in enumerate(arr)]
        arr = sorted(arr, reverse=True)
        ans = [0] * len(arr)
        pointer = 0
        for i in range(len(arr) - 1):
            while pointer < len(arr) - 1 and i >= arr[pointer][1]:
                pointer += 1
            ans[i] = arr[pointer][0]
        ans[-1] = -1
        return ans