[LeetCode] Duplicate Zeros

Question

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.
Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

리스트가 주어질 때, 0만 duplicate 한 뒤에 다른 요소들을 오른쪽으로 한 칸씩 shift 하는 문제였다. (shift 할 때마다 리스트의 맨 마지막 요소는 잘린다.)

Example

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

Solution 1

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        
        num=len(arr) # 처음 arr 길이
        cnt=0 # while문 종료 위한
        idx=0 # 인덱스
        t=0 # 추가한 0의 개수
        
        while True:
            if cnt==num:
                break
            if arr[idx]==0:
                arr.insert(idx+1,0) # 다음 인덱스에 0 추가
                idx+=1
                t+=1
            cnt+=1
            idx+=1
                
        # arr의 길이 맞추기위해 t개의 요소 pop
        for i in range(t):
            arr.pop()

• 직접 푼 풀이이다.
• 지정한 인덱스(=i)에 요소(=x)를 추가하고 싶을 때는 arr.insert(i,x)

Solution 2

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """

        tmp=len(arr)
        idx=0
        cnt=0
        
        while True:
            if idx>=tmp: # idx==tmp가 아님!
                break
                
            if arr[idx]==0:
                arr.insert(idx+1,0)
                arr.pop()
                idx+=2
            else:
                idx+=1

• 직접 푼 풀이이다.
• pop()을 마지막에 한꺼번에 하지 않고 insert()를 한번 할 때마다 바로 하면 코드가 간결해진다.

Solution 3

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """

        answer_tmp=[]
        
        for x in arr:
            answer_tmp.append(x)
            if x==0:
                answer_tmp.append(0)
            
        answer=answer_tmp[:len(arr)]
        
        # 깊은 복사 # arr=answer 이런식으로 얕은 복사하면 안됨!
        for i in range(len(arr)):
            arr[i]=answer[i]

• 다른 분의 풀이이다.
• answer_tmp라는 빈 리스트를 만든 후에 arr의 원소들을 하나씩 집어넣는다. (이때 0은 두번 집어넣는다.)
• 이후에 answer이라는 정답리스트에 answer_tmp의 요소들을 slice해서 대입한다.
• 마지막으로 arr 리스트에 “깊은 복사”를 한다.

끄적

• shift 하면 맨 마지막 요소가 잘리면서 리스트의 전체 길이는 변함없다.
• 얕은 복사를 해서 에러가 날 때에는 깊은 복사를 하자!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기