[LeetCode] 75번 - Sort Colors [Swift]

문제 링크

Sort Colors - LeetCode

문제

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.

문제 풀이

이 문제는 red, white, blue를 나타내는 0,1,2라는 숫자 배열이 주어지는데 이들을 정렬하는 문제입니다.

단순히 정렬 메서드를 사용해서 정렬 할 수도 있는데, 저는 계수 정렬이라는 방법을 사용했습니다.

계수 정렬은 정렬해야하는 숫자들의 범위를 알고 있을 때 각각의 숫자의 개수를 세서 정렬하는 방법인데요, 주어진 배열의 숫자를 모두 세야하기 때문에 시간 복잡도는 O(N)이 나오게 됩니다.

이 문제에서는 0,1,2를 정렬하는 문제이고 모든 0,1,2의 개수를 센 뒤 이들의 개수를 사용하여 배열의 값을 바꿔주면 됩니다.

 

예를 들어 [2,0,1] 이라는 입력이 들어왔다면 0: 1개, 1: 1개, 2: 1개 라고 먼저 세주고 이들을 순서와 개수에 맞게 배열로 만들어주시면 됩니다.

소스 코드

class Solution {
    func sortColors(_ nums: inout [Int]) {
        var hashTable: [Int: Int] = [:]
        hashTable[0] = 0
        hashTable[1] = 0
        hashTable[2] = 0
        
        for i in nums {
            hashTable[i]! += 1
        }
        
        let red: [Int] = [Int](repeating: 0, count: hashTable[0]!)
        let white: [Int] = [Int](repeating: 1, count: hashTable[1]!)
        let blue: [Int] = [Int](repeating: 2, count: hashTable[2]!)
        
        nums = red + white + blue
    }
}