[Leetcode] 75. Sort Colors

<문제 설명>

0,1,2로 된 배열을 작은 순으로 정렬을 하는데 라이브러리를 사용하지 않고 해결하는 것이다.

물론 라이브러리를 사용해도 문제 해결은 가능하지만 이는 정렬에 대한 내용을 이해하고 있는지 점검하기 위한 것이 목표인 문제인 것 같다.

 

<나의 풀이>

일반적으로는 스왑을 하는 sort알고리즘으로 풀면되고 nlogn의 복잡도를 가지는 알고리즘을 사용해도 좋다.

하지만 nlogn의 복잡도를 가지는 알고리즘은 구현하기에 너무 까다롭고 일반적인 알고리즘은 O(n^2)이라서 효율이 좋지 않다. 이번에는 O(n)의 복잡도로 풀어보라는 미션을 주셔서 O(n)이 되도록 풀어보았다.

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zeros = []
        ones = []
        twos = []
        for color in nums:
            if color == 0:
                zeros.append(0)
            elif color == 1:
                ones.append(1)
            else:
                twos.append(2)
                
        nums[:] = zeros + ones + twos

문제에서는 return을 할 필요없이 직접 배열을 바꾸라고 되어있었으므로 새로운 배열을 만들어 return 했다.

 

1. 새로운 배열을 3개 생성한다.

2. 0, 1, 2가 나올 때마다 각각에 해당하는 배열에 값을 추가해준다.

3. 마지막에 배열을 합쳐서 덮어쓴다.

 

간단한 알고리즘이지만 여러번 돌지 않고 한 번의 배열 탐색으로만 문제를 해결할 수 있아서 O(n)의 복잡도로 풀어보았다.

여기서 새로 알게 된 것은 nums에 그냥 대입해서 참조시키면 Wrong이 뜬다는 것인데 nums[:]를 해서 대입을 해주면 성공이 뜬다.

 

 

<nums와 nums[:]의 차이>

정확히 어떤 개념인지 헷갈려서 찾아보니 아래와 같은 이유가 있었다.

https://stackoverflow.com/questions/57152755/difference-between-nums-nums-1-and-nums-nums-1

Difference between nums[:] = nums[::-1] and nums = nums[::-1]

이 문제의 경우 함수를 실행시키는 방식인데, 이렇게 하면 함수 내부에서 할당을 해 주어도 함수가 끝나는 순간 그 값이 유지되지 않는다.

실제로 VsCode에서 함수 바깥에서 실행을 시켜본 결과, 값이 바껴서 잘 나오는 것을 볼 수 있었다.

nums = [2, 1, 0]

zeros = []
ones = []
twos = []
for color in nums:
    if color == 0:
        zeros.append(0)
    elif color == 1:
            ones.append(1)
    else:
        twos.append(2)

nums = zeros + ones + twos

print(nums) #결과값은 [0, 1, 2]

위의 사진처럼 그냥 대입을 하는 것은 새로운 값을 생성하고 그것을 참조하는 방식이고 함수가 끝나면 원래 값은 바뀌지 않은 상태가 되는 것이다. 즉, 원본은 남아있다.

반면, nums[ : ]에 대입하는 방식은 기존의 nums값을 할당하는 값으로 바꾸기 때문에 원본 자체가 바뀌게 된다. 그래서 함수가 끝난 뒤에도 바뀐 값을 유지할 수 있는 것이다.

 

이를 통해, 함수 안에서 값을 바꾸고, 그 바꾼 값을 이용해야 한다면 단순히 할당하지 말고 원본을 바꾸는 방법인지를 꼭 생각해야 한다.