Algorithm) 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기
2022 KAKAO TECH INTERNSHIP 의 두 번째 문제 “두 큐 합 같게 만들기”
최근에 진행된 코딩테스트 문제가 공개가 되었다. 그래서인지 swift 풀이가 많이 없어서 내가 해결한 방법을 올려본다.
실패 - 정확성(56.7/100)
import Foundation
// 아이디어 :
// L > R이라면, queue1의 원소를 queue2로 넘겨줍니다.
// L < R이라면, queue2의 원소를 queue1로 넘겨줍니다.
// Swift 에서는 queue 가 없기 때문에 배열을 사용하여 진행.
// 정확성(56.7/100)
func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
var answer: Int = 0
var queue1 = queue1
var queue2 = queue2
let queue1Sum: Int = queue1.reduce(0, +)
let queue2Sum: Int = queue2.reduce(0, +)
let goal: Int = (queue1Sum + queue2Sum) / 2
if (queue1Sum + queue2Sum) % 2 != 0 {
return -1
} else if goal < queue1.max()! || goal < queue2.max()! {
// 목표값보다 큐의 최대값이 크면 달성할 수 없음.
return -1
}
while goal != queue1.reduce(0, +) {
if queue1.reduce(0, +) > queue2.reduce(0, +) {
let first = queue1.removeFirst()
queue2.append(first)
} else {
let first = queue2.removeFirst()
queue1.append(first)
}
answer += 1
}
return answer
}
실패 - 정확성(83.3 / 100)
import Foundation
// 어렴풋이 reduce 를 통한 합을 구하는 방법에 대한 개선이 필요하다고 느꼈고, 최소한으로 횟수를 가져갔다.
// 하지만, 시간 초과에 부딪혔다.
// 정확성(83.3 / 100)
func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
var answer: Int = 0
var queue1 = queue1
var queue2 = queue2
var queue1Sum: Int = queue1.reduce(0, +)
var queue2Sum: Int = queue2.reduce(0, +)
let goal: Int = (queue1Sum + queue2Sum) / 2
if (queue1Sum + queue2Sum) % 2 != 0 {
return -1
} else if goal < queue1.max()! || goal < queue2.max()! {
// 목표값보다 큐의 최대값이 크면 달성할 수 없음.
return -1
}
while goal != queue1Sum {
if queue1Sum > queue2Sum {
let first = queue1.removeFirst()
queue2.append(first)
// 아이디어: reduce 과정을 통한 시간을 줄이기 위한 과정.
queue1Sum -= first
queue2Sum += first
} else {
let first = queue2.removeFirst()
queue1.append(first)
queue2Sum -= first
queue1Sum += first
}
answer += 1
}
return answer
}
성공 (정확성, 효율성)
import Foundation
// 아이디어 : 투포인터
// 큐에서 다른 큐로 insert 할 때 뒤에 붙는 것을 고려.
// queue1 과 queue2 를 이어서 한 개의 배열에서 두 개의 포인터를 사용.
func solution(_ queue1:[Int], _ queue2:[Int]) -> Int {
let array: [Int] = queue1 + queue2
// queue1 의 좌우 포인터.
var left: Int = 0
var right: Int = queue1.count
var answer: Int = 0
var queue1Sum: Int = queue1.reduce(0, +)
let queue2Sum: Int = queue2.reduce(0, +)
let goal: Int = (queue1Sum + queue2Sum) / 2
if (queue1Sum + queue2Sum) % 2 != 0 {
return -1
}
if goal < queue1.max()! || goal < queue2.max()! {
return -1
}
while right < array.count && left <= right {
if queue1Sum < goal {
// queue1 이 목표값보다 작으면 queue2 에서 이동.
queue1Sum += array[right]
right += 1
} else if queue1Sum > goal {
// queue1 이 목표값보다 크면 queueu2 로 이동.
queue1Sum -= array[left]
left += 1
} else {
// goal 과 같은 경우.
break
}
answer += 1
}
// 이동이 마친 후에도 goal 에 도달하지 않는 경우.
if queue1Sum != goal {
return -1
}
return answer
}
풀이 코드에서 아래의 코드가 있는데 큐 사이에 이동 없이 이루어질 수 없는 조건에 대해서 구현해보았다. 이 코드를 통해 풀이 시간을 단축할 수 있겠다는 예상이 있었다.
if goal < queue1.max()! || goal < queue2.max()! {
return -1
}
결과
주석처리한 코드보다 오래 걸렸다. max() 메소드를 다루는 것이 큐 사이 이동없이 초기에 불가능한 문제에 대해 체크하는 것보다 오버헤드가 컸던 것 같다.