[Kotlin] Programmers Lv. 2 튜플

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

---

문제

---

Code

import java.util.LinkedList
import java.util.Queue

fun main() {
    println(solution(intArrayOf(2,3,7,2), intArrayOf(4,6,5,1)))
}

fun solution(queue1: IntArray, queue2: IntArray): Int {
    var answer: Int = 0
    val size = queue1.size
    var max = size * 3

    val q1: Queue<Int> = LinkedList()
    var q1Sum: Long = 0
    val q2: Queue<Int> = LinkedList()
    var q2Sum: Long = 0

    // 큐 생성
    repeat(size){
        q1Sum += queue1[it].toLong()
        q1.offer(queue1[it])
    }
    repeat(size){
        q2Sum += queue2[it].toLong()
        q2.offer(queue2[it])
    }

    // 계산
    repeat(max){
        if (q1Sum == q2Sum) return answer // 성공조건
        if (q1Sum > q2Sum){
            var num = q1.poll()
            q1Sum -= num
            q2Sum += num
            q2.offer(num)
            answer++
        }
        else if (q1Sum < q2Sum){
            var num = q2.poll()
            q1Sum += num
            q2Sum -= num
            q1.offer(num)
            answer++
        }
    }

    return -1
}

---

풀이

이 문제는 설명속에 풀이가 있다. 그리고 생각해보면 큐의 특성상 어쩔수 없는 풀이법이다.

 

두개의 큐가 존재하고, 그 두개의 값을 동일하게 맞추어야 한다. 그렇다면, 내부 값을 이동시켜서 맞춘다면 어떻게 해야할까?당연히 두개의 큐 중에서 내부 값의 합이 더 큰 쪽이 있을것이다. 그럼 더 큰쪽에서 작은쪽으로 값을 이동시켜주면 된다.더 큰 큐에서 하나빼고, 더 작은큐로 하나 넣는 과정이 1회 이다. 1회를 진행하고, 두개의 값을 비교한다. 같지않다면 반복하면 된다.

 

그렇다면 아무리 반복해도 두 큐의 합이 같아지는 경우가 없는 경우는 어떻게 검출할까?맥시멈 움직이는 방법은 하나의 큐를 다른 한쪽으로 전부 움직이고, 거기있는 나머지 값까지 원래 큐로 전부 움직이는 방법이다. 그렇기때문에 한개 큐의 size에 3을 곱해줬다. 즉 size * 3 만큼 실행했는데 같아지지 않는다면, 불가능 하다는 것이다.

 

여기서 핵심은 sum이다. 처음에는 나도 큐를 생성하고, 큐에 존재하는 내장함수인 sum()을 활용해서 문제를 풀었다. 그런데 이런 방식을 사용한다면 시간 초과가 난다. sum()함수는 O(n)이기때문에 시간이 오래 걸린다. 그러므로 sum이라는 변수에 저장해서 빼는 값만큼 빼고 더하는 값만큼 더한다면  O(1)의 시간복잡도로 시간을 아낄 수 있다.