[leetcode] Replace Elements with Greatest Element on Right Side

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

 

 

arr 가 주어진다.

arr 를 index i를 이용하여 순회한다.

순회하면서 i 이후의 값 중에 최대값을 i에 넣는다.

마지막은 -1 이어야 한다.

 

세 가지 방법이 있고, 마지막 방법이 제일 나은 방법이다.

 

 

 

 

1. 2중 for문 이용하는 방법

 

바로 생각나는 2중 for문 알고리즘이다.

 

class Solution {
    public int[] replaceElements(int[] arr) {
        int last = arr.length-1;
        for(int i=0; i<last; i++){
            arr[i]=findMax(i+1, arr);
        }
        arr[last]=-1;
        return arr;
    }
    
    public int findMax(int i, int[] arr){
        int size = arr.length;
        int max = -1;
        for(;i<size; i++){
            if(max<arr[i]) max=arr[i];
        }
        return max;
    }
}

 

시간이 172ms 걸린다.

무지하게 많이 걸리지만 통과는 된다.

하지만 이게 답이 아니라는 걸 말 하지 않아도 알고 있다.

 

 

 

 

 

2. TreeMap 을 이용하는 방법

 

TreeMap(혹은 TreeSet)을 이용하게 되면, 넣는 족족 정렬이 된다.

정말 편하디 편한 자료구조가 아닐 수 없다.

넣는 시간(logN)과 재정렬하는 시간(logN)을 제외하고 최대값을 가져오는 last 는 O(1) 시간을 갖는다.

 

class Solution {
    public int[] replaceElements(int[] arr) {
       	TreeMap<Integer,Integer> map = new TreeMap<>();
		for(int key : arr){
			int value = 1;
			if(map.containsKey(key)) value = map.get(key)+1;
			map.put(key, value);
	    }
		
	    int size = arr.length;
	    for(int i=0; i<size-1; i++){
	        int key = arr[i];
	        int value = map.get(key);
	        if(value==1) map.remove(key);
	        else map.put(key, value-1);
	        arr[i]=map.lastKey();
	    }
        arr[size-1]=-1;
        return arr;
    }
}

 

map 에 arr 의 값을 키로 두고, 그 키 값의 횟수를 value 로 둔다.

arr 를 순회하는 동안 arr의 index i 값을 map 에서 하나 줄인다.

만약 map 의 i 값이 1 이라면 map 자체에서 지워버린다.

그 후 남아있는 map 의 key 중에서 last 를 이용하여 최댓값을 가져온다.

그 가져온 최댓값을 arr 의 index i 자리에 넣는다.

 

이거 나름대로 괜찮다고 생각했다.

시간도 36ms 밖에 걸리지 않는데.. 그 보다 더 나은 방법이 아래 있다.

 

 

 

 

3. 마지막 max 를 유지하는 방법

 

위의 코드처럼 TreeMap 등을 써서 max 값을 따로 계산 할 필요 없이,

그냥 arr 를 뒤에서 순회해가면서 최댓값을 유지하면 된다.

발상은 "index i 이후의 값 중에 최대값"이라는 문장에서 나온다.

 

class Solution {
    public int[] replaceElements(int[] arr) {
        int max = -1;
        for(int i=arr.length-1; i>=0; i--){
            int v = arr[i];
            arr[i]=max;
            max = Math.max(v,max);
        }
        return arr;
    }
}

 

arr 를 뒤에서 순회해간다.

arr 의 index i 값을 일단 변수 v로 백업해두고,

내가 유지하고 있는 max 값을 arr 의 index i 자리에 넣는다.

그 후 max 값을 백업한 v와 현재 갖고 있는 max 값 둘 중 큰 값으로 교체한다.

 

 

이렇게 짧아도 제 역할에 충실한 코드가 세상에 또 있을까.

콜럼버스의 달걀 저리가라다.