•
문제 링크 : leetcode.com
•
문제 설명 : 숫자들이 존재하는 배열 내부에서 0이 존재하면, 0을 복제한다. 단, 제공된 배열 내부에서 작업이 진행되어야하며 처음 제공된 길이와 동일해야한다.
•
풀이 방법
◦
0을 발견하면 0을 배열의 맨 뒤로 추가한 후, 버블 정렬을 통한 이동을 해주었다.
•
시간복잡도 :
•
성공 코드
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
cursor = 0
len_arr = len(arr)
count = 0
while cursor < len_arr:
if arr[cursor] == 0:
arr.append(0)
for i in range(len(arr) - 1, cursor, -1):
arr[i], arr[i - 1] = arr[i - 1], arr[i]
cursor += 2
count += 1
else:
cursor += 1
for _ in range(count):
arr.pop()
Python
복사
•
개선 코드(Solution 코드) → O(N)
순회 방향으로 데이터를 확인하여 작업하기 때문에, 역방향으로 접근하는 방식을 사용했다.
이 코드의 접근 방법은 0을 어떻게 넣느냐가 아닌 0이 아닌 숫자를 어떻게 이동시키느냐가 핵심이다.
맨 뒤에서부터 접근하면, 0이 아닌 숫자가 최종적으로 얼마나 이동되어야하는지 미리 알 수 있기 때문에 In-place 형식의 연산도 가능하다.
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
zeroes = arr.count(0)
n = len(arr)
# 배열 역순 탐색
for i in range(n - 1, -1, -1):
# 현 숫자가 복제된 0이 모두 들어와도 배열 내 존재할 경우, 미리 해당 위치로 변경
if i + zeroes < n:
arr[i + zeroes] = arr[i]
# 만약 현 숫자가 0일 경우, 0 갯수를 감소하며 복제될 0의 위치의 0 설정
if arr[i] == 0:
zeroes -= 1
if i + zeroes < n:
arr[i + zeroes] = 0
Python
복사