<프로그래머스> 두 큐 합 같게 만들기(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%91%90%20%ED%81%90%20%ED%95%A9%20%EA%B0%99%EA%B2%8C%20%EB%A7%8C%EB%93%A4%EA%B8%B0

[프로그래머스]

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

 

문제는 길었지만 생각보다 쉽게 풀리는 문제였다.

22년도 카카오 인턴쉽 문제였다는데 이게 아마 쉬운 문제에 속하는 게 아니었을까 생각이 든다.

 

이 문제는 제출했을 때 몇 번 틀렸지만 주된 알고리즘이 틀린 게 아니라 곁가지들이 틀렸던 거였다.

내가 짠 코드는 입력값들을 큐에 저장하고 큐를 순회하면서 값이 같지 않고 한쪽이 클 때 거기서 숫자를 하나 빼서 작은 쪽에 넣는 거를 값이 같아질 때까지 반복하도록 했다.

여기서 포인트는 시간 복잡도를 생각해서  sumOf 이런 함수를 쓰지 않기 위해 변수를 따로 설정했다는 것과 반복문의 탈출 조건을 큐들이 다른 큐에 갔다가 다시 돌아오는 걸 생각해서 (두 큐의 사이즈 * 2)로 했다는 것이다.

 

제출했을 때 틀렸던 부분들은 두가지였다.

첫번째는 반복문의 범위를 너무 작게 잡은 거였다.

이 부분은 위에서 말했다시피 사이즈를 더 크게 잡았더니 통과했다.

처음에는 두 큐의 사이즈로만 했는데 생각해보니 이렇게 하면 최악의 상황에 서로 큐가 교체되는 상황까지만 가게 되는 거더라

그래서 2배로 사이즈를 키웠다.

두번째는 자료형 문제였다.

제한사항에도 Long 타입을 고려할 필요가 있다고 했지만 무시하고 그냥 진행했었는데 역시나 Long 타입을 안 하니까 틀린 거였다.

값을 저장하는 변수를 Long 타입으로 변경하니까 통과했다.

(틀렸던 코드들도 깃허브에 올라가있다.)

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    fun solution(queue1: IntArray, queue2: IntArray): Int {
        var answer: Int = 0
        // 큐1
        val q1 = ArrayDeque<Int>()
        // 큐1 원소의 합
        var q1Sum: Long = 0
        // 큐1
        val q2 = ArrayDeque<Int>()
        // 큐2 원소의 합
        var q2Sum: Long = 0

        // 입력값 큐에 저장
        queue1.forEach {
            q1.add(it)
            q1Sum += it
        }
        queue2.forEach {
            q2.add(it)
            q2Sum += it
        }

        while (answer != (q1.size + q2.size) * 2) {
            if (q1Sum > q2Sum) {
                val r = q1.removeFirst()
                q1Sum -= r
                q2Sum += r
                q2.add(r)
                answer++
            } else if (q1Sum < q2Sum) {
                val r = q2.removeFirst()
                q2Sum -= r
                q1Sum += r
                q1.add(r)
                answer++
            } else {
                break
            }
        }

        return if (answer == (q1.size + q2.size) * 2) -1 else answer
    }
}

 

풀면서 신기했던 거는 Int 타입으로 할 때보다 Long 타입으로 할 때 시간이 좀 덜 걸리더라

왜인지 잘 모르겠다...?