Skip to content

[Algorithm] TapeEquilibriumย #133

@hwangJi-dev

Description

@hwangJi-dev

๐Ÿ’ฌย ๋ฌธ์ œ

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


๐Ÿ’ฌย Idea

  • ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์‹ ๊ฒฝ์“ฐ๊ธฐ ์œ„ํ•ด ์ตœ๋Œ€ O(N)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์‚ฌ์šฉํ•˜๋ ค๊ณ  ํ–ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ ํ•ฉ์„ ๊ตฌํ•˜๋Š” reduce๋ฅผ ๋ฐ˜๋ณต๋ฌธ ๋‚ด์— ์œ„์น˜์‹œํ‚ค์ง€ ์•Š๊ณ  ์ด 1ํšŒ ์‚ฌ์šฉํ•˜์—ฌ ๋ณ€์ˆ˜์— ์ดํ•ฉ์„ ์ €์žฅํ•ด๋‘” ํ›„ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ฉฐ ํ•ด๋‹น ๊ฐ’์—์„œ ์›์†Œ์˜ ๊ฐ’์„ ๋นผ์ฃผ๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ–ˆ๋‹ค.

๐Ÿ’ฌย ํ’€์ด

import Foundation
import Glibc

// you can write to stdout for debugging purposes, e.g.
// print("this is a debug message")

public func solution(_ A : inout [Int]) -> Int {
    var asum = 0
    var bsum = A.reduce(0, +)
    var minInterval = 1000000000000000000
    
    for i in 0..<A.count - 1 {
        asum += A[i]
        bsum -= A[i]
        minInterval = min(abs(asum - bsum), minInterval)
    }
    
    return minInterval
}

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

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

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

  • ๋ฌธ์ œ์—์„œ ๋น„์–ด์žˆ์ง€ ์•Š์€ ๋ฐฐ์—ด์ผ ๊ฒฝ์šฐ์—๋งŒ ์ฐจ๋ฅผ ๊ตฌํ•ด์ค€๋‹ค๋Š” ์กฐ๊ฑด์ด ์žˆ์—ˆ๋Š”๋ฐ ํ•ด๋‹น ์กฐ๊ฑด์„ ๋ฌด์‹œํ•˜๊ณ  ๋งˆ์ง€๋ง‰ ์›์†Œ๊นŒ์ง€ ์ดํ•ฉ์—์„œ ๋นผ์„œ ์ฐจ๋ฅผ ๊ตฌํ•˜๋Š” ์‹ค์ˆ˜๋ฅผ ๋ฒ”ํ–ˆ๋‹ค.. ์•ž์œผ๋กœ ๋ฌธ์ œ ๋” ๊ผผ๊ผผํžˆ ์ฝ๊ธฐ..!!!!

Metadata

Metadata

Assignees

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions