๐Ÿ“– Problem Solution/Programmers

[Swift] 2022 KAKAO TECH INTERNSHIP ๋‘ ํ ํ•ฉ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ

Fomagran ๐Ÿ’ป 2022. 8. 24. 11:30
728x90
๋ฐ˜์‘ํ˜•

Problem

 

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr


Solution

 

๋‚˜๋Š” ์ด๋ฒˆ ๋ฌธ์ œ๋ฅผ ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ(Sliding-Window)๋ฅผ ์ด์šฉํ•ด์„œ ํ’€์—ˆ๋‹ค.

 

1. ํ•„์š”ํ•œ ๋ณ€์ˆ˜๋ฅผ ์„ธํŒ…ํ•œ๋‹ค.

 

cumulativeSum: ๋ˆ„์ ํ•ฉ์„ ๋‹ด์„ ๋ฐฐ์—ด

q1Length: queue1์˜ ๊ธธ์ด

q2Length: queue2์˜ ๊ธธ์ด

answer: ๊ฐ€์žฅ ์ ์€ ์ž‘์—… ํšŸ์ˆ˜๋ฅผ ๊ธฐ๋กํ•  ๋ณ€์ˆ˜

start: ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ์—์„œ ์‹œ์ž‘ ์ง€์ ์„ ๊ฐ€๋ฅดํ‚ฌ ๋ณ€์ˆ˜

 

    var cumulativeSum: [Int] = [0]
    let q1Length: Int = queue1.count
    let q2Length: Int = queue2.count
    var answer: Int = Int.max
    var start: Int = 0

 

2. queue1๊ณผ queue2์˜ ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•ด์ค€๋‹ค.

 

    for q in queue1 + queue2 {
        let last = cumulativeSum.last!
        cumulativeSum.append(last + q)
    }

 

3. ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ ์ „ ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ๋“ค์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

๋งŒ์•ฝ ํ•ฉ์ด ํ™€์ˆ˜๋ผ๋ฉด ๋‘ ํ ํ•ฉ์„ ๊ฐ™๊ฒŒ ๋งŒ๋“ค ์ˆ˜ ์—†์œผ๋ฏ€๋กœ -1์„ ๋ฐ˜ํ™˜ํ•˜๊ณ ,

 

๋งŒ์•ฝ queue1์˜ ํ•ฉ์ด ์ด ํ•ฉ์˜ ์ ˆ๋ฐ˜์ด๋ผ๋ฉด ์ด๋™์ด ํ•„์š” ์—†์œผ๋ฏ€๋กœ 0์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

    let halfTotal: Int = cumulativeSum.last!/2
    
    if cumulativeSum.last!%2 == 1 {
        return -1
    }
    
    if cumulativeSum[q1Length] == halfTotal {
        return 0
    }

 

4. ๋ˆ„์ ํ•ฉ์„ ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ๋ฅผ ํ†ตํ•ด ์ ˆ๋ฐ˜ ํ•ฉ์ด ๋˜๋Š” ์ง€์ ์„ ์ฐพ์•„๋‚ธ๋‹ค.

 

๋งŒ์•ฝ ์ ˆ๋ฐ˜ํ•ฉ๋ณด๋‹ค ํฌ๋‹ค๋ฉด start๋ฅผ ๋Š˜๋ ค ๊ธธ์ด๋ฅผ ์ค„์—ฌ์ฃผ๊ณ , 

 

์ ˆ๋ฐ˜ํ•ฉ๋ณด๋‹ค ํฌ๋‹ค๋ฉด ๋‹ค์Œ i๋กœ ๋„˜์–ด๊ฐ€ ๊ธธ์ด๋ฅผ ๋Š˜๋ ค์ค€๋‹ค.

 

๋งŒ์•ฝ ๊ทธ ์™€์ค‘์— ์ ˆ๋ฐ˜ ํ•ฉ๊ณผ ๊ฐ™์€ ๊ฒƒ์ด ์žˆ๋‹ค๋ฉด getWorkCount๋กœ ์ž‘์—… ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•ด์ฃผ๊ณ , ์ตœ์†Œ๊ฐ’์„ ๊ฐฑ์‹ ํ•œ๋‹ค.

 

    for i in 1..<cumulativeSum.count {
        if cumulativeSum[i] - cumulativeSum[start] > halfTotal {
            while cumulativeSum[i] - cumulativeSum[start] > halfTotal {
                start += 1
            }
        }
        
        if cumulativeSum[i] - cumulativeSum[start] == halfTotal {
            answer = min(answer,getWorkCount(l: start, r: i-1))
        }
    }

 

5. ์‹œ์ž‘๊ณผ ๋ ์ง€์ ์— ๋”ฐ๋ผ ์ž‘์—… ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•ด์ค€๋‹ค.

 

๊ธธ์ด์˜ ์‹œ์ž‘๊ณผ ๋์€ ์ด 4๊ฐ€์ง€์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋‹ค.

 

 5-1. ์‹œ์ž‘์ด queue1์— ์žˆ๊ณ  ๋๋„ queue1์— ์žˆ๋Š” ๊ฒฝ์šฐ

 

์‹œ์ž‘ ์ง€์ ๋ถ€ํ„ฐ ๋ ์ง€์ ๊นŒ์ง€ queue2๋กœ ์ด๋™ํ•˜๊ณ  queue2์˜ ์ „์ฒด๋ฅผ queue1์œผ๋กœ ์ด๋™ํ•ด ์ค˜์•ผ ํ•˜๋ฏ€๋กœ 

 

l(์‹œ์ž‘ ์ง€์ ) + r(๋ ์ง€์ ) + q2Length + 1์ด ๋œ๋‹ค.

 

 5-2. ์‹œ์ž‘์ด queue1์— ์žˆ๊ณ  ๋์ด queue1์˜ ๋์ธ ๊ฒฝ์šฐ

 

์ด ๊ฒฝ์šฐ๋Š” ์‹œ์ž‘ ์ง€์  ์•ž์˜ ์›์†Œ๋งŒ queue2๋กœ ์ด๋™์‹œ์ผœ ์ฃผ๋ฉด ๋˜๋ฏ€๋กœ l(์‹œ์ž‘ ์ง€์ )์ด ๋œ๋‹ค.

 

 5-3. ์‹œ์ž‘์ด queue1์— ์žˆ๊ณ  ๋์ด queue2์— ์žˆ๋Š” ๊ฒฝ์šฐ

 

์ด ๊ฒฝ์šฐ์—” ์‹œ์ž‘ ์ง€์  ์ „๊นŒ์ง€์˜ ์›์†Œ๋ฅผ queue2๋กœ ๋ณด๋‚ด๊ณ , ๋ ์ง€์ ์˜ queue2 ์›์†Œ๋ฅผ queue1์œผ๋กœ ๋ณด๋‚ด๋ฉด ๋˜๋ฏ€๋กœ

 

l(์‹œ์ž‘ ์ง€์ ) + r(๋ ์ง€์ ) + q1Lentgh + 1์ด ๋œ๋‹ค.

 

 5-4. ์‹œ์ž‘์ด queue2์— ์žˆ๊ณ  ๋์ด queue2์— ์žˆ๋Š” ๊ฒฝ์šฐ

 

๋ ์ง€์  ๋งŒํผ ๋ชจ๋‘ queue2๋กœ ์˜ฎ๊ธฐ๊ณ  ์‹œ์ž‘ ์ง€์ ์—์„œ q1Length๋งŒํผ ๋บ€ ๊ฐ’์„ ์˜ฎ๊ฒจ ์ค˜์•ผ ํ•˜๋ฏ€๋กœ

 

r(๋ ์ง€์ () + l(์‹œ์ž‘ ์ง€์ ) - q1Length + 1์ด ๋œ๋‹ค.

 

    func getWorkCount(l: Int, r: Int) -> Int {
        if 0..<q1Length ~= l {
            if r == q1Length - 1 {
                return l
            }
            if 0..<q1Length ~= r {
                return l + r + q2Length + 1
            } else {
                return l + r - q1Length + 1
            }
        }
        
        return r + (l-q1Length) + 1
    }

Result

 

์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์šฐ์„  ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด queue1๊ณผ queue2๋ฅผ ์ˆœํšŒํ•˜๊ณ , ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ๋กœ ์ตœ์†Œ๊ฐ’์„ ๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— queue1๊ณผ queue2๋ฅผ ํ•œ๋ฒˆ ๋” ์ˆœํšŒํ•œ๋‹ค.

 

queue1 + queue2์˜ ๊ธธ์ด๋ฅผ n์ด๋ผ๊ณ  ๊ฐ€์ •ํ•  ๋•Œ 2n์ด ์†Œ์š”๋˜๋ฏ€๋กœ O(n)์ด ์†Œ์š”๋œ๋‹ค.

 

๊ณต๊ฐ„ ๋ณต์žก๋„๋Š” ๋ˆ„์ ํ•ฉ์„ queue1 + queue2์˜ ๊ธธ์ด๋งŒํผ ์ €์žฅํ•˜๋ฏ€๋กœ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ O(n)์ด ์†Œ์š”๋œ๋‹ค.


Source Code

 

import Foundation

func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
    var cumulativeSum: [Int] = [0]
    let q1Length: Int = queue1.count
    let q2Length: Int = queue2.count
    var answer: Int = Int.max
    var start: Int = 0
    
    for q in queue1 + queue2 {
        let last = cumulativeSum.last!
        cumulativeSum.append(last + q)
    }
    
    let halfTotal: Int = cumulativeSum.last!/2
    
    if cumulativeSum.last!%2 == 1 {
        return -1
    }
    
    if cumulativeSum[q1Length] == halfTotal {
        return 0
    }
    
    func getWorkCount(l: Int, r: Int) -> Int {
        if 0..<q1Length ~= l {
            if r == q1Length - 1 {
                return l
            }
            if 0..<q1Length ~= r {
                return l + r + q2Length + 1
            } else {
                return l + r - q1Length + 1
            }
        }
        
        return r + (l-q1Length) + 1 
    }
    
    for i in 1..<cumulativeSum.count {
        if cumulativeSum[i] - cumulativeSum[start] > halfTotal {
            while cumulativeSum[i] - cumulativeSum[start] > halfTotal {
                start += 1
            }
        }
        
        if cumulativeSum[i] - cumulativeSum[start] == halfTotal {
            answer = min(answer,getWorkCount(l: start, r: i-1))
        }
    }
    
    return answer == Int.max ? -1 : answer
}
728x90
๋ฐ˜์‘ํ˜•