[LeetCode] Replace Elements with Greatest Element on Right Side

Question

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

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

Constraints

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

Solution 1

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        
        res=[0]*len(arr)
        res[-1]=-1

        # res를 뒤에서부터 채우는 방법
        for i in range(len(arr)-2, -1, -1): # i는 len(arr)-2 부터 0까지 -1씩 점프
            res[i]=max(res[i+1], arr[i+1])

        return res

• 다른 분의 풀이이다.
• Time Limit Exceeded가 발생하지 않는다.
• res를 뒤에서 부터 채운다.
• res[i]는 res[i+1]과 arr[i+1] 중에 더 큰 값이다.

Solution 2

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        
        res=[]
        max_num=0
        if len(arr)==1:
            res.append(-1)
            return res
        for i in range(len(arr)-1):
            for j in range(i+1, len(arr)):
                # max_num 개신
                if arr[j]>max_num:
                    max_num=arr[j]
            res.append(max_num)
            max_num=0
        res.append(-1)
        return res

• 직접 푼 풀이이다.
• Time Limit Exceeded가 발생한다ㅠ

Solution 3

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        
        tmp=[]
        res=[]
        if len(arr)==1:
            res.append(-1)
            return res
        for i in range(len(arr)-1):
            for j in range(i+1,len(arr)):
                tmp.append(arr[j])
            # max() 사용
            res.append(max(tmp))
            tmp.clear()
        res.append(-1)
        return res

• 직접 푼 풀이이다.
• 마찬가지로 Time Limit Exceeded가 발생한다ㅠ

끄적

• 시간 초과때문에 고생한 문제였다..

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기