[Leetcode] 75. Sort Colors

문제)

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

 

Example 1:

Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1] Output: [0,1,2]

Example 3:

Input: nums = [0] Output: [0]

Example 4:

Input: nums = [1] Output: [1]

 

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is 0, 1, or 2.

풀이)

아래는 내 개인 IDE에서는 잘 나오는데, 리트코드 제출하면 결과값이 제대로 적용 안되는 코드....

println해도 값는 잘 정렬되어서 잘 들어간게 확인되는데, 결과값은 왜 반영이 안되는지 모르겠는 코드..

class Solution {
    public int[] sortColors(int[] nums) {
        int[] result = new int[nums.length];
        int idx = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) == null) {
                map.put(nums[i],1);
            } else {
                map.put(nums[i], map.get(nums[i])+1);
            }
        }

        for(int i = 0; i < 3; i++) {
            if(map.get(i) == null) continue;
            for (int j = 0; j < map.get(i); j++) {
                result[idx] = i;
                idx++;
            }
        }
        
        return result;
    }
}

1. 설명
 - map를 사용해서 color를 key로, 해당 color의 갯수를 value로 입력
 - for문을 통해서 하나의 리스트로 만들어서 리턴

 

2. 제출결과

 println하면 결과는 잘 나오는데, 제출결과는 입력값이 그대로 출력됨.

왜인지 모르겠음..

 

3. 시간복잡도

O(n)

 

다른사람 풀이1)

public void sortColors(int[] nums) {
    // 1-pass
    int p1 = 0, p2 = nums.length - 1, index = 0;
    while (index <= p2) {
        if (nums[index] == 0) {
            nums[index] = nums[p1];
            nums[p1] = 0;
            p1++;
        }
        if (nums[index] == 2) {
            nums[index] = nums[p2];
            nums[p2] = 2;
            p2--;
            index--;
        }
        index++;
    }
}

 

다른사람 풀이 2)

public void sortColors(int[] nums) {
    // 2-pass
    int count0 = 0, count1 = 0, count2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {count0++;}
        if (nums[i] == 1) {count1++;}
        if (nums[i] == 2) {count2++;}
    }
    for(int i = 0; i < nums.length; i++) {
        if (i < count0) {nums[i] = 0;}
        else if (i < count0 + count1) {nums[i] = 1;}
        else {nums[i] = 2;}
    }
}