-
[leetcode] Replace Elements with Greatest Element on Right Side알고리즘 2021. 11. 13. 15:49
Description
정수 배열이 주어졌을때, 특정 인덱스를 순회하여 자신보다 큰 값이 나오면 특정 인덱스부터 큰 값의 인덱스 사이의 값들을 모두 큰 값으로 바꿔주는 문제. 단, 마지막 원소는 항상 -1 값을 넣어주어야 한다.
Input: arr = [17, 18, 5, 4, 6, 1]
Output: [18, 6, 6, 6, 1, -1]
Input: arr = [400]
Output: [-1]
Success
배열 뒤에서 부터 순회하며 현재 값이 앞에 있는 값들보다 큰 경우 모두 현재 값으로 바꿔준다.
배열 원소가 하나남았을때 다시 반대로 순회하며 배열을 한칸씩 앞으로 채워 -1 값이 들어갈 자리를 만들어준다.
class Solution { public int[] replaceElements(int[] arr) { if(arr == null || arr.length == 1) { return new int[]{-1}; } for(int i=arr.length-1; i>=1; i--) { if(arr[i] > arr[i-1]) { arr[i-1] = arr[i]; } if (i == 1) { for(int j=1; j<arr.length; j++) { arr[j-1] = arr[j]; if (j == arr.length-1) { arr[j] = -1; } } } } return arr; } }
Leetcode Solution
위 방법은 완전 비효율적이였다. 아래와 같이 배열 마지막 값을 max 값으로 초기화한 후 -1 값으로 세팅주고 뒤에서 두번째 인덱스부터 배열을 순회하며 max 값을 계속해서 넣어주는 방법으로하면 시간복잡도를 훨씬 단축시킬 수 있다.
class Solution { public int[] replaceElements(int[] arr) { int n=arr.length-1; int max=arr[n]; arr[n] = -1; for(int i=n-1;i>=0;i--){ int curr = arr[i]; arr[i] = max; if(max<curr) max=curr; } return arr; } }
출처
'알고리즘' 카테고리의 다른 글
[leetcode] 283. Move Zeroes (0) 2021.11.19 [leetcode] 26. Remove Duplicates from Sorted Array (0) 2021.11.16 [leetcode] 941. Valid Mountain Array (0) 2021.11.12 [leetcode] Check If N and Its Double Exist (0) 2021.11.12 [leetcode] 27. Remove Element (0) 2021.11.09