[Leetcode][75. Sort Colors ] 75. Sort Colors 코딩 인터뷰 문제풀이 Java

75. Sort Colors 문제풀이

Sort Colors - LeetCode

 

이 밑에 방법은, 내가 먼저 혼자 가지고 나온 방법이다. HashMap을 사용할때, 꽤나 유용하게 쓰일 수 있는 `getOrDefault`에 대한 syntax하고 방법도 다시 리마인드가 되어서 좋은 문제라고 생각을 하고 풀었었다. 

HashMap getOrDefault(key, defaultValue) method in Java with Examples - GeeksforGeeks

class Solution {
    public void sortColors(int[] nums) {
        
        Map<Integer, Integer> frequencyByColor = new HashMap();
        for (int num: nums) {
            frequencyByColor.put(num, frequencyByColor.getOrDefault(num,0)+1);
        }
        
        int redFrequency = frequencyByColor.getOrDefault(0, 0);
        int whiteFrequency = frequencyByColor.getOrDefault(1, 0);
        int blueFrequency = frequencyByColor.getOrDefault(2, 0);
        
        int startNewIndex = 0;
        while(redFrequency > 0) {
            nums[startNewIndex++] = 0;
            redFrequency--;
        }

        while(whiteFrequency > 0) {
            nums[startNewIndex++] = 1;
            whiteFrequency--;
        }
        
        while(blueFrequency > 0) {
            nums[startNewIndex++] = 2;
            blueFrequency--;
        }         
    }
}

하지만, 밑에 Submission 결과에도 나오듯이, 결코 효율적 efficient한 방법론은 아닌것 같다. 왜냐면, Runtime속도적으로도 굉장히 느리고, 게다가 메모리도 많이 쓴 방법으로, 이 문제에서 원하는 최적의 방법은 아니다. (물론, 내가 한 방법이 "틀리다"는 아니지만, 코드를 읽어보면, while loop 자체를 3번씩이나 쓰고 있다. 당연히, 최적화 할 수 있는 틈이 있다는 말이고, 꽤나 의심의 눈초리로 문제에 대한 해결책을 submit 해 보았다. 그런데 어쩜, 거기서 나온 결과는.. 당연하게도 최적화가 아니라고 했다. 

그러다가, Forum에서 하는 설명을 들어보니, Sorting 중에서도 Counting Sort이라는 기법이 있다고 했다. 

도저히 혼자서는 못하겠다는 생각이여서ㅎㅎ (그동안 코딩인터뷰 준비를 하도 안했더니ㅎㅎ), 다시한번 튜토리얼을 보면서 이해하기 시작했다. 

    public void sortColors(int[] nums) {
        if(nums.length == 1 || nums.length == 0) return;
        
        int start = 0;
        int end = nums.length - 1;
        int currentIndex = 0;
        
        while(start < end && currentIndex <= end) {
            if(nums[currentIndex] == 0) { // to make sure all 0s are upfront
                //swap 0s
                nums[currentIndex] = nums[start];
                nums[start] = 0;
                start++;
                currentIndex++;
            } else if(nums[currentIndex] == 2) { //to make sure all 2s are at back
                nums[currentIndex] = nums[end];
                nums[end] = 2;
                end--;
            } else { 
                currentIndex++;
            }
        }
    }

어쩜, 그렇게 했더니, 전 submission과는 확실하게 다르게, 너무나도 Runtime 그리고 Memory usage도 깔끔하게 나왔다ㅎㅎ. 

여기서 중요한 포인트는 바로, 2를 swap할 때에는, currentIndex자체를 decrement하지 않았다는 것인데, 이유는 바로 최악의 case인 when we have to swap 0 from the middle of them이다. 

 

예를 들자면, [0, 0, 1, 1, 2, 0] input이 있다고 가정해 보자. 여기서, 만약에, currentIndex가 4이고, 마지막 end 의 index가 마지막 nums array 사이즈 일 때이다. 그러면, 우리가 결국은 swap하고, currnetIndex조차도 바꿔버리게 되면은, [0, 0, 1, 1, 0, 2] 가 되버리는 건데.. 그러면 0 가 array맨 앞으로 오는 것이 아니라, 뜬금없이 그 중간에 있게되는 불상사가 생길 수가 있다는 것이다. 그리고, 이미 currentIndex 자체가 nums array의 마지막까지 다았기 때문에, 결국 이 while loop은 나올거고, 그러면 이 상태로 nums array가 set되어버리는 거다.. 그렇기에, currentIndex는 나두고, 마지막까지, 인덱스가 가고, 결국엔 한번 더 while loop이 돌게 되고, 그로 인해서 첫번째 if statement가 들어가면서, 다시한번 0자체가 그 앞으로 가게 되는 현상을 불러 일으키는거다. (정말 설명을 듣고나서는, "와.. 이걸 짧은 인터뷰시간에 어떻게 최적화한 상태의 대답을 가져올 수 있을까 하는 의문이 드는건 사실이다. 그래도 막상 오랜만에 문제풀니깐 재밌긴하다ㅎㅎ)