Skip to content

[Algorithm] FirstUniqueย #157

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

https://app.codility.com/programmers/trainings/4/first_unique/


๐Ÿ’ฌย Idea

  • ์™„์ „ํƒ์ƒ‰์„ ํ†ตํ•ด Dictionary์— ํ•ด๋‹น key๊ฐ’์ด ์ฒ˜์Œ ๋‚˜ํƒ€๋‚ฌ์„ ๋•Œ์˜ index์™€ key๊ฐ’์ด ๋ช‡๋ฒˆ ๋‚˜ํƒ€๋‚ฌ๋Š”์ง€๋ฅผ ์ €์žฅํ•œ๋‹ค.
  • ์ดํ›„ ๊ฐ’์ด ๊ณ ์œ ํ•˜์ง€ ์•Š์€ ๊ฒƒ๋“ค์„ ๋ชจ๋‘ ํ•„ํ„ฐ๋งํ•œ ๋’ค index๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ฒซ key๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค. ์ด ๋•Œ ๋นˆ ๋ฐฐ์—ด์ด๋ผ๋ฉด -1์„ ๋ฆฌํ„ดํ•œ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

public func solution(_ A : inout [Int]) -> Int {
    var dict: [Int: (Int, Int)] = [:]
    
    if A.count == 1 { return A.first! }
    if A.count == 0 { return -1 }
    
    for (index, i) in A.enumerated() {
        if dict[i] == nil {
            dict[i] = (index, 1)
        } else {
            dict[i]!.1 += 1
        }
    }
    
    dict = dict.filter({ $0.value.1 == 1 })
    return dict.sorted(by: { $0.value.0 < $1.value.0 }).first?.key ?? -1
}

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

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

ํ‰๊ฐ€ํ‘œ : https://app.codility.com/demo/results/trainingV9V5FJ-6NK/

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions