> 문제
배열의 element중 값이 0인 경우 위와 같이 배열의 뒤로 보내고 기존 숫자들의 순서는 유지하는 알고리즘입니다.
0을 찾아 맨 끝으로 보내고 맨 끝에 있는 수를 앞으로 한칸씩 움직여서 그 0의 자리로 보낼 수도 있지만 operation이 복잡해집니다.
또는 0을 찾아서 한칸씩 bubble swap을 시킬 수 있지만 0을 찾을 때마다 bubble swap을 한다는 것은 너무 많은 operation이 발생하고 time complexity는 O(n * #0)가 됩니다.
> solution1_swap
'0이 아닌 수를 찾는 index'와 '항상 0을 가리키는 index'를 정의합니다.
둘 모두의 첫 index는 0입니다.
('항상 0을 가리키는 index'라는 이름이 약간 헷갈리기도 하네요)
'0이 아닌 수를 찾는 index'가 한칸씩 오른쪽으로 이동하다가 0이 아닌 수를 찾으면 0과 swap을 하고 '항상 0을 가리키는 index'를 1칸 오른쪽으로 옮겨줍니다.
(예시처럼 시작 부분의 숫자가 0이 아닌 경우 둘은 swap이 일어나지만 표면적인 변화는 없으며, '항상 0을 가리키는 index'는 1칸 옮겨지게 됩니다.)
'0이 아닌 수를 찾는 index'의 루프가 끝나면서 최종 완료됩니다.
▶︎ code
array = [3, 9, 0, 1, 0, 29, 30]
def move_zero(values):
zero_location = 0
for i in range(len(values)):
if values[i] != 0:
values[zero_location], values[i] = values[i], values[zero_location]
zero_location += 1
return values
print(move_zero(array))> solution2_copy
'0이 아닌 수를 찾는 index'와 '항상 0을 가리키는 index'를 정의합니다.
둘 모두의 첫 index는 0입니다.
(swap과 마찬가지로 '항상 0을 가리키는 index'라는 이름이 알맞지는 않는 것 같습니다.)
'0이 아닌 수를 찾는 index'가 0이 아닌 수를 만나면 그 값을 복사하여 '항상 0을 가리키는 index'에 있는 값을 해당 값으로 변경시킵니다.
위와 같은 경우 표면적으로는 변화가 없지만 0이 아닌 수를 만났기 때문에 해당 인덱스의 값은 실재로 복사되어 대체되었습니다.
'0이 아닌 수를 찾는 index'가 0이 아닌 수를 만나면 해당 값을 복사하여 '항상 0을 가리키는 index'가 가리키는 0을 대체합니다.
이후 '항상 0을 가리키는 index'는 오른 쪽으로 한칸 옮겨지게 되고 '0이 아닌 수를 찾는 index'는 다시 0이 아닌 숫자를 찾아 이동하고 복사/대체를 반복합니다.
'0이 아닌 수를 찾는 index'의 루프가 끝나면 '항상 0을 가리키는 index'가 가리키는 위치부터 배열의 끝 까지 0을 덮어 써주면 최종 완료됩니다.
▶︎ code
array = [3, 9, 0, 1, 0, 29, 30]
def move_zero(values):
zero_location = 0
for i in range(len(values)):
if values[i] != 0:
values[zero_location] = values[i]
zero_location += 1
while zero_location < len(values):
values[zero_location] = 0
zero_location += 1
return values
print(move_zero(array))출처: 코드없는 프로그래밍
