자료구조 - 배열 문제 : 0 이동시키기

연습문제 : 0 이동시키기

여러 개의 0과 양의 정수들이 섞여 있는 배열이 주어짐. 이 배열에서 0들은 전부 뒤로 빼내고, 나머지 숫자들의 순서는 그대로 유지한 배열을 반환하는 함수를 만들어봐.

 

예를 들어서, [0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0] 가 입력으로 주어졌을 경우 [8, 37, 4, 5, 50, 34, 0, 0, 0, 0, 0, 0] 을 반환하면 됨. 공간 복잡도 O(1)으로 이 문제를 풀 수 있음?

def moveZerosToEnd(nums):
    return nums

def main():
    print(moveZerosToEnd([0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0]))

if __name__ == "__main__":
    main()

>>>

def moveZerosToEnd(nums):
    currentPosition = 0    # 0이 아닌 애들이 들어갈 위치
    
    for i in range(len(nums)):    # 배열을 돌면서 
        if nums[i] != 0:    # 0이 아니면
            nums[currentPosition] = nums[i]    # currentPosition을 이용해 앞으로 밀어버리고
            if i != currentPosition:    # 앞으로 밀려서 비게된 공간만큼 0으로 채워주는거
                nums[i] = 0
            currentPosition += 1
    
    return nums

def main():
    print(moveZerosToEnd([0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0]))

if __name__ == "__main__":
    main()

nums의 크기를 N이라고 했을 때,

새로운 변수는 currentPosition 밖에 없음. 

이 함수의 Big-O 공간복잡도 = O(1)