Skip to content

[Algorithm] MissingIntegerย #137

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/


๐Ÿ’ฌย Idea

  • N ์ •์ˆ˜์˜ ๋ฐฐ์—ด A๊ฐ€ ์ฃผ์–ด์ง€๋ฉด A์—์„œ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š” ๊ฐ€์žฅ ์ž‘์€ ์–‘์˜ ์ •์ˆ˜(0๋ณด๋‹ค ํผ)๋ฅผ ๋ฐ˜ํ™˜ํ•ด์•ผ ํ•˜๋ฏ€๋กœ
  • ์šฐ์„  A๋ฅผ ์ •๋ ฌํ•œ ๋’ค A์—์„œ 1๋ณด๋‹ค ์ž‘์€ ์ˆ˜๋ฅผ ๋ชจ๋‘ ํ•„ํ„ฐ๋งํ•ด์ฃผ์—ˆ๋‹ค.
  • ์ดํ›„ ๊ฒฐ๊ณผ๊ฐ€ ๋นˆ ๋ฐฐ์—ด์ด๋ผ๋ฉด 1์„ ๋ฆฌํ„ดํ•˜์—ฌ ๋นจ๋ฆฌ ๊ฒฐ๊ณผ๊ฐ’์„ ๋„์ถœํ•ด์ฃผ์—ˆ๊ณ , ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด for๋ฌธ์„ ๋Œ๋ฉฐ preInteger(์ด์ „ ์ •์ˆ˜ ๊ฐ’)์™€ ์ •๋ ฌ๋œ ์›์†Œ์˜ ๊ฐ’์„ ๋น„๊ตํ•˜๋ฉฐ ๊ทธ ์ฐจ์ด๊ฐ€ 1 ์ดˆ๊ณผ์ธ ๊ฒฝ์šฐ์— ๊ฐ€์žฅ ์ž‘์€ ์–‘์˜ ์ •์ˆ˜๋ฅผ ๋„์ถœํ•˜๊ธฐ ์œ„ํ•ด preInteger + 1 ์„ ๋ฆฌํ„ดํ•ด์ฃผ์—ˆ๋‹ค.
  • ๋งŒ์•ฝ for๋ฌธ์„ ๋‹ค ๋Œ๊ณ ๋„ ๊ฐ€์žฅ ์ž‘์€ ์ •์ˆ˜๋ฅผ ์ฐพ์ง€ ๋ชปํ–ˆ๋‹ค๋ฉด 1 ์ด์ƒ์˜ ๋ชจ๋“  ์›์†Œ๊ฐ€ ์ฑ„์›Œ์ ธ์žˆ๋Š” ๊ฒƒ์ด๋ฏ€๋กœ Set(A)์˜ ๊ฐœ์ˆ˜ + 1์„ ํ•ด์„œ ๊ทธ ๋‹ค์Œ์œผ๋กœ ์ž‘์€ ์ˆ˜๋ฅผ ๋ฆฌํ„ดํ•ด์ฃผ์—ˆ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

import Foundation

public func solution(A : inout [Int]) -> Int {
    A = A.sorted()
    A = A.filter({ $0 >= 1 })
    
    if A.isEmpty { return 1 }
    
    var preInteger = 0
    
    for i in A {
        if i - preInteger > 1 {
            return preInteger + 1
        } else {
            preInteger = i
        }
    }
    
    return Set(A).count + 1
}

์†Œ์š”์‹œ๊ฐ„ : 16๋ถ„

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N) or O(N * log(N))

ํ‰๊ฐ€ํ‘œ : https://app.codility.com/demo/results/trainingK7RBSR-4DF/

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions