[프로그래머스][Kotlin][2022 KAKAO TECH INTERNSHIP] 두 큐 합 같게 만들기

import java.util.*
class Solution {
    fun solution(queue1: IntArray, queue2: IntArray): Int {
        var answer: Int = 0
        var sum1 = queue1.sum().toLong()
        var sum2 = queue2.sum().toLong()
        var que1 = ArrayDeque<Long>()
        var que2 = ArrayDeque<Long>()
        for(i in 0 .. queue1.size-1){ 
            que1.add(queue1[i].toLong())
            que2.add(queue2[i].toLong())
        }
        val stopCheck = (que1.size+1) * 2
        while(true){
            if(sum1 > sum2){
                que2.add(que1.peekFirst())
                sum2 += que1.peekFirst()
                sum1 -= que1.peekFirst()
                que1.removeFirst()
                answer++
            } else if(sum1 < sum2){
                que1.add(que2.peekFirst())
                sum1 += que2.peekFirst()
                sum2 -= que2.peekFirst()
                que2.removeFirst()
                answer++
            } else {
                break
            }
            if(answer > stopCheck){
                answer = -1
                break
            }
        }
        return answer
    }
}

해당 코드를 작성하면서 2가지의 실수를 하였었습니다. 

첫번째로는 break 조건을 잘못 설정했다는 점이였습니다.

 

pop 과정과 insert 과정의 한계점을 잘못지정하여 작업을 더 수행하지 못하여 잘못된 결과가 나왔었습니다.

 

두번째로는 while 문 내에서 sum 문을 사용하여 시간복잡도가 O(N^2) 가 되어 시간초과로 통과를 못하였습니다.

 

작성 후 생각해보니 sum은 해당 자료를 끝까지 조회하며 값을 계산하는 함수라 시간 초과가 날 수 밖에 없구나라고 생각하여 큐 별로 처음에 한번씩 sum()를 계산 후 변수에 저장한 뒤에 작업이 진행될때마다 변수에 값을 변경하는 방식으로 진행하여 시간 초과 없이 통과 할 수 있었습니다.

해당 문제를 풀고나서 코드를 작성하면서도 시간 복잡도를 좀 더 생각하면서 풀어야 추후 코딩테스트 및 app 코드 수정 및 작성 시 문제가 생기지 않고 문제가 생기지 않더라도 더욱 빠른 코드를 작성 할 수 있겠구나 라고 생각 및 반성 하였습니다.

상기 코드는 현재 저의 실력으로 작성하였으며, 추후 새로 알게된 개념등을 알게 된다면 다시 작성 할 수 있도록 하겠습니다.

상기코드의 실행 결과 입니다.

테스트 1 〉	통과 (15.98ms, 63.1MB)
테스트 2 〉	통과 (16.98ms, 62.7MB)
테스트 3 〉	통과 (18.70ms, 62.8MB)
테스트 4 〉	통과 (14.14ms, 63.1MB)
테스트 5 〉	통과 (16.15ms, 63.2MB)
테스트 6 〉	통과 (14.40ms, 62.9MB)
테스트 7 〉	통과 (17.98ms, 62.8MB)
테스트 8 〉	통과 (13.95ms, 63MB)
테스트 9 〉	통과 (21.84ms, 62.4MB)
테스트 10 〉	통과 (16.09ms, 63.4MB)
테스트 11 〉	통과 (32.05ms, 71MB)
테스트 12 〉	통과 (32.09ms, 71.2MB)
테스트 13 〉	통과 (39.54ms, 72.2MB)
테스트 14 〉	통과 (31.50ms, 72.2MB)
테스트 15 〉	통과 (29.96ms, 79.1MB)
테스트 16 〉	통과 (31.34ms, 84.7MB)
테스트 17 〉	통과 (33.53ms, 82.9MB)
테스트 18 〉	통과 (85.88ms, 112MB)
테스트 19 〉	통과 (55.61ms, 126MB)
테스트 20 〉	통과 (77.11ms, 120MB)
테스트 21 〉	통과 (80.99ms, 127MB)
테스트 22 〉	통과 (90.33ms, 127MB)
테스트 23 〉	통과 (55.16ms, 127MB)
테스트 24 〉	통과 (67.17ms, 127MB)
테스트 25 〉	통과 (16.72ms, 63.7MB)
테스트 26 〉	통과 (14.06ms, 62.8MB)
테스트 27 〉	통과 (14.77ms, 63.1MB)
테스트 28 〉	통과 (36.32ms, 79.2MB)
테스트 29 〉	통과 (15.86ms, 64.7MB)
테스트 30 〉	통과 (54.13ms, 79.7MB)