Problem
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
}
'๐ Problem Solution > Programmers' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] 2022 KAKAO TECH INTERNSHIP ๋ฑ์ฐ์ฝ์ค ์ ํ๊ธฐ (0) | 2022.08.29 |
---|---|
[Swift] 2022 KAKAO TECH INTERNSHIP ์ฝ๋ฉ ํ ์คํธ ๊ณต๋ถ (0) | 2022.08.26 |
[Swift] 2022 KAKAO TECH INTERNSHIP ์ฑ๊ฒฉ ์ ํ ๊ฒ์ฌํ๊ธฐ (1) | 2022.08.23 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค ์ซ์์ ํํ (0) | 2022.04.11 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค ๊ฐ์ ์ซ์๋ ์ซ์ด (0) | 2022.04.11 |
๋๊ธ