๋ฌธ์ ์ค๋ช
๊ธธ์ด๊ฐ ๊ฐ์ ๋ ๊ฐ์ ํ๊ฐ ์ฃผ์ด์ง๋๋ค. ํ๋์ ํ๋ฅผ ๊ณจ๋ผ ์์๋ฅผ ์ถ์ถ(pop)ํ๊ณ , ์ถ์ถ๋ ์์๋ฅผ ๋ค๋ฅธ ํ์ ์ง์ด๋ฃ๋(insert) ์์ ์ ํตํด ๊ฐ ํ์ ์์ ํฉ์ด ๊ฐ๋๋ก ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ์ด๋ ํ์ํ ์์ ์ ์ต์ ํ์๋ฅผ ๊ตฌํ๊ณ ์ ํฉ๋๋ค. ํ ๋ฒ์ pop๊ณผ ํ ๋ฒ์ insert๋ฅผ ํฉ์ณ์ ์์ ์ 1ํ ์ํํ ๊ฒ์ผ๋ก ๊ฐ์ฃผํฉ๋๋ค.
ํ๋ ๋จผ์ ์ง์ด๋ฃ์ ์์๊ฐ ๋จผ์ ๋์ค๋ ๊ตฌ์กฐ์ ๋๋ค. ์ด ๋ฌธ์ ์์๋ ํ๋ฅผ ๋ฐฐ์ด๋ก ํํํ๋ฉฐ, ์์๊ฐ ๋ฐฐ์ด ์์ชฝ์ ์์์๋ก ๋จผ์ ์ง์ด๋ฃ์ ์์์์ ์๋ฏธํฉ๋๋ค. ์ฆ, pop์ ํ๋ฉด ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ์์๊ฐ ์ถ์ถ๋๋ฉฐ, insert๋ฅผ ํ๋ฉด ๋ฐฐ์ด์ ๋์ ์์๊ฐ ์ถ๊ฐ๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด ํ [1, 2, 3, 4]๊ฐ ์ฃผ์ด์ก์ ๋, pop์ ํ๋ฉด ๋งจ ์์ ์๋ ์์ 1์ด ์ถ์ถ๋์ด [2, 3, 4]๊ฐ ๋๋ฉฐ, ์ด์ด์ 5๋ฅผ insertํ๋ฉด [2, 3, 4, 5]๊ฐ ๋ฉ๋๋ค.
๋ค์์ ๋ ํ๋ฅผ ๋ํ๋ด๋ ์์์ ๋๋ค.
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]
๋ ํ์ ๋ด๊ธด ๋ชจ๋ ์์์ ํฉ์ 30์ ๋๋ค. ๋ฐ๋ผ์, ๊ฐ ํ์ ํฉ์ 15๋ก ๋ง๋ค์ด์ผ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ๋ค์๊ณผ ๊ฐ์ด 2๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์ต๋๋ค.
- queue2์ 4, 6, 5๋ฅผ ์์๋๋ก ์ถ์ถํ์ฌ queue1์ ์ถ๊ฐํ ๋ค, queue1์ 3, 2, 7, 2๋ฅผ ์์๋๋ก ์ถ์ถํ์ฌ queue2์ ์ถ๊ฐํฉ๋๋ค. ๊ทธ ๊ฒฐ๊ณผ queue1์ [4, 6, 5], queue2๋ [1, 3, 2, 7, 2]๊ฐ ๋๋ฉฐ, ๊ฐ ํ์ ์์ ํฉ์ 15๋ก ๊ฐ์ต๋๋ค. ์ด ๋ฐฉ๋ฒ์ ์์ ์ 7๋ฒ ์ํํฉ๋๋ค.
- queue1์์ 3์ ์ถ์ถํ์ฌ queue2์ ์ถ๊ฐํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ queue2์์ 4๋ฅผ ์ถ์ถํ์ฌ queue1์ ์ถ๊ฐํฉ๋๋ค. ๊ทธ ๊ฒฐ๊ณผ queue1์ [2, 7, 2, 4], queue2๋ [6, 5, 1, 3]๊ฐ ๋๋ฉฐ, ๊ฐ ํ์ ์์ ํฉ์ 15๋ก ๊ฐ์ต๋๋ค. ์ด ๋ฐฉ๋ฒ์ ์์ ์ 2๋ฒ๋ง ์ํํ๋ฉฐ, ์ด๋ณด๋ค ์ ์ ํ์๋ก ๋ชฉํ๋ฅผ ๋ฌ์ฑํ ์ ์์ต๋๋ค.
๋ฐ๋ผ์ ๊ฐ ํ์ ์์ ํฉ์ ๊ฐ๊ฒ ๋ง๋ค๊ธฐ ์ํด ํ์ํ ์์ ์ ์ต์ ํ์๋ 2์ ๋๋ค.
๊ธธ์ด๊ฐ ๊ฐ์ ๋ ๊ฐ์ ํ๋ฅผ ๋ํ๋ด๋ ์ ์ ๋ฐฐ์ด queue1, queue2๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ๊ฐ ํ์ ์์ ํฉ์ ๊ฐ๊ฒ ๋ง๋ค๊ธฐ ์ํด ํ์ํ ์์ ์ ์ต์ ํ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ๋จ, ์ด๋ค ๋ฐฉ๋ฒ์ผ๋ก๋ ๊ฐ ํ์ ์์ ํฉ์ ๊ฐ๊ฒ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ, -1์ return ํด์ฃผ์ธ์.
๋ฌธ์ ํ์ด
ํ์ ์ฒซ ๋ฒ์งธ ์์๋ฅผ popํ๊ณ ๋ค์ ์์๋ฅผ ๋ฐฐ์นํ๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋ O(n) ์ด๋ค.
๋ ํ๋ฅผ ํฉ์น๊ณ (totalQueue), leftOffset๊ณผ rightOffset์ ์ค์ ํด left๋ 0๋ฒ์งธ, right๋ queue2์ ์์์ ์ ๊ธฐ์ค์ผ๋ก ์ค์ ํ๋ค.
๋ฐ๋ผ์ leftOffset์ด rightOffset์ ์ด๊ณผํ๋ ๊ฒฝ์ฐ์ ๋ชจ๋ pop๊ณผ์ ์ด ๋๋๊ฒ ๋๋ฉฐ, rightOffset์ด totalQueue์ ๊ธธ์ด๊ฐ ๋์ด๊ฐ๋ฉด ๋ชจ๋ ๋น๊ตํ ์ ์๋ ๊ฒฝ์ฐ์ ์๊ฐ ๋๋๊ฒ ๋๋ค.
์ดํ ๊ฐ์ ๋น๊ตํ๋ ๊ณผ์ ์ queue1์ ํฉ์ด ๋ชจ๋ ์์์ ํ๊ท ๊ฐ(totalQueueAverage)๋ณด๋ค ํฌ๋ฉด queue1์์ pop์ด ์ผ์ด๋๋ฏ๋ก queue1Sum์์ leftOffset์ ์์นํ ๊ฐ์ ๋นผ์ฃผ๊ณ leftOffset์ 1 ์ฆ๊ฐ์ํจ๋ค.
๋ฐ๋๋ก queue1์ ํฉ์ด ๋ชจ๋ ์์์ ํ๊ท ๊ฐ(totalQueueAverage)๋ณด๋ค ์์ผ๋ฉด queue2์์ pop์ด ์ผ์ด๋๋ฏ๋ก queue1Sum์ rightOffset์ ์์นํ ๊ฐ์ ๋ํ๊ณ rightOffset์ 1 ์ฆ๊ฐ์ํจ๋ค.
๊ฒฐ๊ณผ์ ์ผ๋ก ์ฌ์ดํด์ด ๋๋ฉด์ queue1Sum๊ณผ totalQueueAverage๊ฐ ๊ฐ์ด์ง ๋, count๋ฅผ ๋ฐํํ๊ฒ ๋๋ค.
๊ทธ๋ฌ๋ ๋ง์ฝ ๋ง์กฑํ ์ ์๋ ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ์ง ์์ while๋ฌธ์ ๋น ์ ธ๋์ค๊ฒ ๋ ๊ฒฝ์ฐ์๋ -1์ ๋ฐํํ๊ฒ ๋๋ค.
import Foundation
func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
var queue1Sum = queue1.reduce(0) {$0 + $1}
var totalQueue = queue1 + queue2
var totalQueueAverage = totalQueue.reduce(0) {$0 + $1} / 2
var leftOffset: Int = 0
var rightOffset: Int = queue1.count
var count: Int = 0
if !(totalQueueAverage is Int) { return -1 }
while (leftOffset <= rightOffset && rightOffset < totalQueue.count) {
if queue1Sum == totalQueueAverage {
return count
}
if queue1Sum > totalQueueAverage {
queue1Sum -= totalQueue[leftOffset]
leftOffset += 1
} else {
queue1Sum += totalQueue[rightOffset]
rightOffset += 1
}
count += 1
}
return -1
}
[ํ๋ก๊ทธ๋๋จธ์ค ๋ฌธ์ ๋งํฌ]
https://school.programmers.co.kr/learn/courses/30/lessons/118667