[Swift] 2022 KAKAO TECH INTERNSHIP 두 큐 합 같게 만들기

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
}