Skip to content

[Algorithm] PermMissingElemย #132

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/


๐Ÿ’ฌย Idea

  • data๊ฐ€ 100,000๊ฐœ ์ด๋‚ด์ด๋ฏ€๋กœ O(N)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๋ฉด ๋˜๊ฒ ๋‹ค๊ณ  ํŒ๋‹จํ–ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ A๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๋’ค for๋ฌธ์„ ๋Œ๋ฉฐ index์™€ ์ผ์น˜ํ•˜์ง€ ์•Š๋Š” ๋ถ€๋ถ„์„ ์ฐพ์•„ ๋ฐ˜ํ™˜ํ•ด์ฃผ์—ˆ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    A = A.sorted()
    
    for i in 0..<A.count {
        if i + 1 != A[i] {
            return i + 1
        }
    }
    
    return A.count + 1
}

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

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

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

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions