.leetcode(1299. Replace Elements with Greatest Element on Right Side)

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

 

1. 2022/04/25 시도

소요시간: 9분(시간복잡도 O(n^2)), 4분(시간복잡도 O(n))

// O(n)
class Solution {
    public int[] replaceElements(int[] arr) {
        int post = arr[arr.length-1];
        arr[arr.length-1] = -1;
        for (int i=arr.length-2; i>=0; i--) {
            int temp = post;
            if (arr[i] > post) {
                post = arr[i];
            }
            arr[i]=temp;
        }
        
        return arr;
    }
}

// O(n^2)
class Solution {
    public int[] replaceElements(int[] arr) {
        int maxIndex = 0;
        for (int i=0; i<arr.length-1; i++) {
            if (i == maxIndex) {
                maxIndex = i+1;
                for (int j=i+1; j<arr.length; j++) {
                    if (arr[maxIndex] < arr[j]) {
                        maxIndex = j;
                    }
                }
            }
            arr[i] = arr[maxIndex];
        }
        arr[arr.length-1] = -1;
        
        return arr;
    }
}

풀이 접근 과정

#1
뒤에서부터 데이터를 세팅해준다.
해당 요소가 세팅될때마다 해당 요소의 값과 기존의 최대값(=post)와 비교해서 post값을 업데이트해주면서 채워간다.
O(n)의 시간복잡도로 풀 수 있다.

#2
전체 arr를 for문으로 순회한다.
대상인덱스를 제외한 오른쪽 데이터 중에 큰 인덱스를 찾는다.

찾은 인덱스 크기가 될때까지 데이터를 세팅한다.
O(n^2)의 시간복잡도로 예상된다.

 

느낀점

• 처음에는 O(n)으로 생각이 잘 안났다. 먼저 O(n^2)부터 풀었다. 그런데 생각해보니 이거 뒤에서부터 오면 왠지 풀 수 있을거 같다는 느낌이 들었다고 다시 풀어서 시간복잡도 O(n)의 결과를 나오게 할 수 있었다.
• 역시 배열은 문제풀기전에 왼쪽,오른쪽 접근 혹은 인덱스를 이용해 풀 수 있는지 정도는 체크해보는게 좋겠다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형