Skip to content

[Algorithm] PassingCarsย #138

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/


๐Ÿ’ฌย Idea

  • P๊ฐ€ Q๋ณด๋‹ค ์ž‘์„ ๋•Œ๋งŒ ์ˆœ์„œ์Œ์ด ๋งŒ๋“ค์–ด์ง„๋‹ค๋Š” ์›๋ฆฌ๋ฅผ ์ด์šฉํ•˜์—ฌ ํ’€์–ด์ฃผ์—ˆ๋‹ค.
  1. ๋จผ์ € ์„œ์ชฝ์œผ๋กœ ํ–ฅํ•˜๋Š” ์ฐจ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜์—ฌ westCarCount์— ์ €์žฅํ•ด๋†“๋Š”๋‹ค.
  2. ์ดํ›„ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉด์„œ
    1. ์ฐจ๊ฐ€ ์„œ์ชฝ์œผ๋กœ ํ–ฅํ•  ๋•Œ๋งˆ๋‹ค westCarCount๋ฅผ -1์”ฉ ์ฐจ๊ฐํ•ด์ฃผ๊ณ 
    2. ๋™์ชฝ์œผ๋กœ ํ–ฅํ•˜๋Š” ์ฐจ๊ฐ€ ๋‚˜์˜ค๋ฉด ๋‹น์‹œ์˜ westCarCount๋ฅผ ans์— ๋”ํ•˜์—ฌ ์ˆœ์„œ์Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋„์ถœํ•ด์ฃผ์—ˆ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

public func solution(_ A : inout [Int]) -> Int {
    var westCarCount = A.filter({ $0 == 1 }).count
    var ans = 0
    
    for a in A {
        if a == 0 {
            ans += westCarCount
        } else {
            westCarCount -= 1
        }
    }
    
    return ans > 1000000000 ? -1 : ans
}

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

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

ํ‰๊ฐ€ํ‘œ : https://app.codility.com/demo/results/trainingYDRNDZ-VG7/

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions