Home > Archive > Leet-Code > ๐Ÿ†™ [LeetCode] 1089.Duplicate Zeros.

๐Ÿ†™ [LeetCode] 1089.Duplicate Zeros.
swift algorithm datastructure

๐Ÿ†™ [LeetCode] 1089.Duplicate Zeros

  • Difficulty: Easy
  • Topic: Array, Two Pointers

๋ฌธ์ œ๋Š” ๋ฐฐ์—ด์„ ์ œ์ž๋ฆฌ์—์„œ ์ˆ˜์ •ํ•˜๋„๋ก ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค.

์ œ์ž๋ฆฌ ์ˆ˜์ •์ด ์ œ์•ฝ ์กฐ๊ฑด์ด ์•„๋‹ˆ๋ผ๋ฉด, ์›๋ณธ ๋ฐฐ์—ด์—์„œ ๋Œ€์ƒ ๋ฐฐ์—ด๋กœ ์š”์†Œ๋ฅผ ๋ณต์‚ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ–ˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.







0์„ ๋‘ ๋ฒˆ ๋ณต์‚ฌํ•œ ๊ฒƒ์„ ์ฃผ๋ชฉํ•˜์„ธ์š”.

var s = 0
var d = 0

let N = source.count // ์—ฌ๊ธฐ์„œ 'source'๋Š” Int ํƒ€์ž…์˜ ๋ฐฐ์—ด์ด๋ผ๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค.
var destination = [Int]()

// ๋ชฉ์ ์ง€ ๋ฐฐ์—ด์ด ๊ฐ€๋“ ์ฐฐ ๋•Œ๊นŒ์ง€ ๋ณต์‚ฌ๊ฐ€ ์ˆ˜ํ–‰๋ฉ๋‹ˆ๋‹ค.
while s < N {
    if source[s] == 0 {
        // 0์„ ๋‘ ๋ฒˆ ๋ณต์‚ฌํ•ฉ๋‹ˆ๋‹ค.
        destination.append(0)
        d += 1
        destination.append(0)
    } else {
        destination.append(source[s])
    }
    
    d += 1
    s += 1
}

๋ฌธ์ œ ์„ค๋ช…์—๋Š” ์ƒˆ ๋ฐฐ์—ด์„ ํ™•์žฅํ•˜์ง€ ์•Š๊ณ  ์›๋ž˜ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋กœ๋งŒ ์ž๋ฅธ๋‹ค๊ณ ๋„ ์–ธ๊ธ‰๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋Š” ๋ฐฐ์—ด์˜ ๋์—์„œ ๋ช‡๋ช‡ ์š”์†Œ๋ฅผ ๋ฒ„๋ ค์•ผ ํ•จ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฌํ•œ ์š”์†Œ๋“ค์€ ์ƒˆ๋กœ์šด ์ธ๋ฑ์Šค๊ฐ€ ์›๋ž˜ ๋ฐฐ์—ด์˜ ๊ธธ์ด๋ฅผ ๋„˜์–ด์„œ๋Š” ์š”์†Œ๋“ค์ž…๋‹ˆ๋‹ค.






์šฐ๋ฆฌ์—๊ฒŒ ์ฃผ์–ด์ง„ ๋ฌธ์ œ ์ œ์•ฝ ์‚ฌํ•ญ์— ๋Œ€ํ•ด ๋‹ค์‹œ ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค.

์ถ”๊ฐ€ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์—, ์šฐ๋ฆฌ์˜ ์›๋ณธ ๋ฐฐ์—ด๊ณผ ๋Œ€์ƒ ๋ฐฐ์—ด์€ ๋ณธ์งˆ์ ์œผ๋กœ ๋™์ผํ•ฉ๋‹ˆ๋‹ค.

์šฐ๋ฆฌ๋Š” ๋‹จ์ˆœํžˆ ์›๋ณธ์„ ๋Œ€์ƒ ๋ฐฐ์—ด๋กœ ๊ทธ๋Œ€๋กœ ๋ณต์‚ฌํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๊ทธ๋ ‡๊ฒŒ ํ•˜๋ฉด ๋ช‡๋ช‡ ์š”์†Œ๋ฅผ ์žƒ์–ด๋ฒ„๋ฆด ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์™œ๋ƒํ•˜๋ฉด, ์šฐ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ๋ฎ์–ด์“ฐ๊ฒŒ ๋  ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.





์ด๋ฅผ ์—ผ๋‘์— ๋‘๊ณ  ์•„๋ž˜ ๊ฒ๊ทผ ๋ฐฉ์‹์—์„œ๋Š” ๋ฐฐ์—ด์˜ ๋ ๋ถ€๋ถ„์— ๋ณต์‚ฌ๋ฅผ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

Approach 1: Two pass, O(1) space

Intuition(์ง๊ด€)

๋งŒ์•ฝ ์šฐ๋ฆฌ๊ฐ€ ๋ฐฐ์—ด์˜ ๋์—์„œ ๋ฒ„๋ ค์งˆ ์š”์†Œ์˜ ์ˆ˜๋ฅผ ์•ˆ๋‹ค๋ฉด, ๋‚˜๋จธ์ง€๋Š” ๋ณต์‚ฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์šฐ๋ฆฌ๋Š” ์–ด๋–ป๊ฒŒ ๋ฐฐ์—ด์˜ ๋์—์„œ ๋ฒ„๋ ค์งˆ ์š”์†Œ์˜ ์ˆ˜๋ฅผ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ์„๊นŒ์š”?

๊ทธ ์ˆ˜๋Š” ๋ฐฐ์—ด์— ์ถ”๊ฐ€๋  ์—ฌ๋ถ„์˜ 0์˜ ์ˆ˜์™€ ๊ฐ™์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์—ฌ๋ถ„์˜ 0์€ ๋ฐฐ์—ด์˜ ๋์—์„œ ์š”์†Œ ํ•˜๋‚˜๋ฅผ ๋ฐ€์–ด๋‚ด๋ฉด์„œ ์ž์‹ ์„ ์œ„ํ•œ ๊ณต๊ฐ„์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค.



์ผ๋‹จ ์šฐ๋ฆฌ๊ฐ€ ์›๋ž˜ ๋ฐฐ์—ด์—์„œ ์ตœ์ข… ๋ฐฐ์—ด์˜ ์ผ๋ถ€๊ฐ€ ๋  ์š”์†Œ์˜ ์ˆ˜๋ฅผ ์•Œ๊ฒŒ ๋˜๋ฉด, ์šฐ๋ฆฌ๋Š” ๋์—์„œ๋ถ€ํ„ฐ ๋ณต์‚ฌํ•˜๊ธฐ ์‹œ์ž‘ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋์—์„œ๋ถ€ํ„ฐ ๋ณต์‚ฌํ•˜๋Š” ๊ฒƒ์€, ๋งˆ์ง€๋ง‰ ๋ช‡ ๊ฐœ์˜ ๋ถˆํ•„์š”ํ•œ ์š”์†Œ๋“ค์„ ๋ฎ์–ด์“ธ ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, ์–ด๋–ค ์š”์†Œ๋„ ์žƒ์–ด๋ฒ„๋ฆฌ์ง€ ์•Š๊ฒŒ ํ•ด์ค๋‹ˆ๋‹ค.

Algorithm

1๏ธโƒฃ. ์ค‘๋ณต๋  ์ œ๋กœ์˜ ์ˆ˜๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ possible_dups๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค.

์ตœ์ข… ๋ฐฐ์—ด์˜ ์ผ๋ถ€๊ฐ€ ๋˜์ง€ ์•Š์„ ์ž˜๋ฆฐ ์ œ๋กœ๋“ค์„ ์„ธ์ง€ ์•Š๋„๋ก ์ฃผ์˜ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๋ฒ„๋ ค์ง„ ์ œ๋กœ๋“ค์€ ์ตœ์ข… ๋ฐฐ์—ด์˜ ์ผ๋ถ€๊ฐ€ ๋˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

possible_dups์˜ ๊ฐœ์ˆ˜๋Š” ์›๋ž˜ ๋ฐฐ์—ด์—์„œ ์ž˜๋ฆด ์š”์†Œ์˜ ์ˆ˜๋ฅผ ์•Œ๋ ค์ค„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ์–ด๋Š์‹œ์ ์—์„œ๋“ , length_ - possible_dups๋Š” ์ตœ์ข… ๋ฐฐ์—ด์— ํฌํ•จ๋  ์š”์†Œ์˜ ์ˆ˜์ž…๋‹ˆ๋‹ค.






์ฐธ๊ณ : ์œ„์˜ ๋‹ค์ด์–ด๊ทธ๋žจ์—์„œ๋Š” ์ดํ•ด๋ฅผ ๋•๊ธฐ ์œ„ํ•ด ์›๋ณธ ๋ฐฐ์—ด๊ณผ ๋Œ€์ƒ ๋ฐฐ์—ด์„ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค

์šฐ๋ฆฌ๋Š” ์ด๋Ÿฌํ•œ ์—ฐ์‚ฐ๋“ค์„ ์˜ค์ง ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์—์„œ๋งŒ ์ˆ˜ํ–‰ํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค.


2๏ธโƒฃ. ๋‚จ์€ ์š”์†Œ๋“ค์˜ ๊ฒฝ๊ณ„์— ์žˆ๋Š” ์ œ๋กœ์— ๋Œ€ํ•œ ์—์ง€ ์ผ€์ด์Šค๋ฅผ ์ฒ˜๋ฆฌํ•ฉ๋‹ˆ๋‹ค.



์ด ๋ฌธ์ œ์˜ ์—์ง€ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ์ด์•ผ๊ธฐํ•ด ๋ด…์‹œ๋‹ค.

๋‚จ์€ ๋ฐฐ์—ด์—์„œ ์ œ๋กœ๋ฅผ ๋ณต์ œํ•  ๋•Œ๋Š” ํŠน๋ณ„ํ•œ ์ฃผ์˜๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

์ด ์ฃผ์˜๋Š” ๊ฒฝ๊ณ„์— ๋†“์ธ Zero์— ๋Œ€ํ•ด์„œ ์ทจํ•ด์ ธ์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์™œ๋ƒํ•˜๋ฉด, ์ด ์ œ๋กœ๋Š” ๊ฐ€๋Šฅํ•œ ์ค‘๋ณต์œผ๋กœ ๊ฐ„์ฃผ๋˜๊ฑฐ๋‚˜, ๊ทธ๊ฒƒ์˜ ๋ณต์ œ๋ฅผ ์ˆ˜์šฉํ•  ๊ณต๊ฐ„์ด ์—†์„ ๋•Œ ๋‚จ์€ ๋ถ€๋ถ„์— ํฌํ•จ๋  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

๋งŒ์•ฝ ๊ทธ๊ฒƒ์ด possible_dups์˜ ์ผ๋ถ€๋ผ๋ฉด ์šฐ๋ฆฌ๋Š” ๊ทธ๊ฒƒ์„ ๋ณต์ œํ•˜๊ณ  ์‹ถ์„ ๊ฒƒ์ด๊ณ , ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ๋ณต์ œํ•˜์ง€ ์•Š์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.


์—์ง€ ์ผ€์ด์Šค์˜ ์˜ˆ๋Š” - [8,4,5,0,0,0,0,7] ์ž…๋‹ˆ๋‹ค.
์ด ๋ฐฐ์—ด์—์„œ ์ฒซ ๋ฒˆ์งธ์™€ ๋‘ ๋ฒˆ์งธ๋กœ ์ œ๋กœ์˜ ์ค‘๋ณต์„ ์ˆ˜์šฉํ•  ๊ณต๊ฐ„์ด ์žˆ์Šต๋‹ˆ๋‹ค.
ํ•˜์ง€๋งŒ ์„ธ๋ฒˆ์งธ ์ œ๋กœ์˜ ์ค‘๋ณต์„ ์œ„ํ•œ ์ถฉ๋ถ„ํ•œ ๊ณต๊ฐ„์ด ์—†์Šต๋‹ˆ๋‹ค.
๋”ฐ๋ผ์„œ ๋ณต์‚ฌํ•  ๋•Œ ์„ธ ๋ฒˆ์งธ ์ œ๋กœ์— ๋Œ€ํ•ด์„  ๋‘ ๋ฒˆ ๋ณต์‚ฌํ•˜์ง€ ์•Š๋„๋ก ์ฃผ์˜ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๊ฒฐ๊ณผ = [8,4,5,0,`0`,0,`0`,0]





3๏ธโƒฃ. ๋ฐฐ์—ด์˜ ๋์—์„œ๋ถ€ํ„ฐ ์ˆœํšŒํ•˜์—ฌ, 0์ด ์•„๋‹Œ ์š”์†Œ๋Š” ํ•œ ๋ฒˆ, 0 ์š”์†Œ๋Š” ๋‘ ๋ฒˆ ๋ณต์‚ฌํ•ฉ๋‹ˆ๋‹ค.

์šฐ๋ฆฌ๊ฐ€ ๋ถˆํ•„์š”ํ•œ ์š”์†Œ๋“ค์„ ๋ฒ„๋ฆฐ๋‹ค๊ณ  ํ•  ๋•Œ, ์ด๋Š” ๋‹จ์ˆœํžˆ ๋ถˆํ•„์š”ํ•œ ์š”์†Œ๋“ค์˜ ์™ผ์ชฝ์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ์ƒˆ๋กœ์šด ๊ฐ’๋“ค๋กœ ๊ทธ๊ฒƒ๋“ค์„ ๋ฎ์–ด์“ฐ๊ณ , ๊ฒฐ๊ตญ ๋‚จ์€ ์š”์†Œ๋“ค์€ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ด๋™์‹œ์ผœ ๋ฐฐ์—ด ์•ˆ์— ์ค‘๋ณต๋œ ์š”์†Œ๋“ค์„ ์œ„ํ•œ ๊ณต๊ฐ„์„ ๋งŒ๋“ค์–ด๋‚ธ๋‹ค๋Š” ๊ฒƒ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.






class Solution {
    func duplicateZeros(_ arr: inout [Int]) {
        var possibleDups = 0
        let length_ = arr.count - 1
        // ๋ณต์ œํ•  0์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค.
        // ์›๋ž˜ ๋ฐฐ์—ด์˜ ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋„˜์–ด์„œ๋ฉด ์ค‘์ง€ํ•ฉ๋‹ˆ๋‹ค.
        // ์ˆ˜์ •๋œ ๋ฐฐ์—ด์˜ ์ผ๋ถ€๊ฐ€ ๋  ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๋„˜์–ด์„œ๋ฉด ์ค‘์ง€ํ•ฉ๋‹ˆ๋‹ค.
        for left in 0...(length_ - possibleDups) {
            // 0 ์ˆซ์ž ์„ธ๊ธฐ
            if arr[left] == 0 {
                // Edge case: ์ด 0์€ ๋ณต์ œํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋” ์ด์ƒ ๊ณต๊ฐ„์ด ์—†์Šต๋‹ˆ๋‹ค.
                // ์™ผ์ชฝ์€ ํฌํ•จ๋  ์ˆ˜ ์žˆ๋Š” ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.
                if left == length_ - possibleDups {
                    // ์ด 0์˜ ๊ฒฝ์šฐ ์ค‘๋ณต ์—†์ด ๋ณต์‚ฌํ•ฉ๋‹ˆ๋‹ค.
                    arr[length_] = 0
                    break
                }
                possibleDups += 1
            }
        }
        
        // ์ƒˆ ๋ฐฐ์—ด์˜ ์ผ๋ถ€๊ฐ€ ๋  ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ถ€ํ„ฐ ๊ฑฐ๊พธ๋กœ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.
        var last = length_ - possibleDups
        
        // 0์„ ๋‘ ๋ฒˆ ๋ณต์‚ฌํ•˜๊ณ  0์ด ์•„๋‹Œ ๊ฒƒ์„ ํ•œ ๋ฒˆ ๋ณต์‚ฌํ•ฉ๋‹ˆ๋‹ค.
        while last >= 0 {
            if arr[last] == 0 {
                arr[last + possibleDups] = 0
                possibleDups -= 1
                arr[last + possibleDups] = 0
            } else {
                arr[last + possibleDups] = arr[last]
            }
            last -= 1
        }
    }
}

Complexity Analysis

  • ์‹œ๊ฐ„ ๋ณต์žก๋„(Time Complexity): O(N), ์—ฌ๊ธฐ์„œ N์€ ๋ฐฐ์—ด์˜ ์š”์†Œ ์ˆ˜์ž…๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ๋‘ ๋ฒˆ ์ˆœํšŒํ•˜๋Š”๋ฐ, ํ•˜๋‚˜๋Š” possible_dups์˜ ์ˆ˜๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด, ๋‹ค๋ฅธ ํ•˜๋‚˜๋Š” ์š”์†Œ๋“ค์„ ๋ณต์‚ฌํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ, ๋ฐฐ์—ด์— zero๊ฐ€ ์ ๊ฑฐ๋‚˜ ์—†์„ ๋•Œ ๋ฐฐ์—ด ์ „์ฒด๋ฅผ ์ˆœํšŒํ•  ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ณต๊ฐ„ ๋ณต์žก๋„(Space Complexity): O(1), ์šฐ๋ฆฌ๋Š” ์ถ”๊ฐ€์ ์ธ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.