문제 보러 가기

[프로그래머스] 두 큐 합 같게 만들기

1. 오답의 가능성

1) 2, 29번 -> 두 큐의 합이 처음부터 같을 경우
2) 27, 28, 29번 -> 큐의 합이 Long 타입이어야 할 경우
3) 시간 초과
-> 적당한 타이밍에 return 을 하지 못해 무한 루프를 돌 경우
-> 배열이 수정될 때마다 .sum() 메소드를 사용하여 구한 경우
-> deque을 사용하지 않고 일반 배열로 0번째 요소를 제거하는 경우

2. var limitLoopCount = queue1.size * 4

• 참고 사이트: 2022 테크 여름 인턴십 코딩테스트 해석

1) queue1.size * 2 라고 생각한 착각
나는 당연히 루프를 끝내야 하는 시기를 두 큐의 총 size 일거라고 생각했다.
하지만 대부분의 해석이 queue1.size * 3 이었고, 이렇게 하면 풀렸기 때문에(?)
영문도 모른채 우선 문제를 풀 때는 저 식을 적용했다.

2) queue1.size * 4 인 이유?
위에 사이트에서 해설을 읽었을 때 내 결론은 queue1.size 3이 아닌 queue1.size 4 였다.

나가야하는 시점은 명확한데, 바로 모든 배열을 돌려봤을 때다.
만약 왼쪽, 오른쪽 길이가 각각 4인 두 큐가 주어졌다고 가정해보자.

• 두 큐를 하나로 합친다.
• L -> R 순서로 완전하게 회전하면 총 8번
• 반대로 R -> L 순서로 완전 회전 총 8번
• 총 16번 (4 * 하나의 배열 길이)

이게 나의 추측이다.. X3 은 이해가 되질 않는다. ㅜㅜ
친절하신 분이 있다면 저에게 설명 좀.. 부탁드립니다.

3. ArrayDeque<Long>()

1) queue1.toMutableList()
intArray는 수정에 있어서 자유롭지 않기 때문에, mutableList로 수정해서 코딩을 했었다.
이렇게 하면 24번에서 계속 시간 초과가 되는 문제가 있었다. (정말 미치는 줄 알았다...)

2) 덱(Deque)을 사용하게 되면 훨씬 빠른 속도로 결과 처리가 가능
deque는 배열의 시작과 끝의 요소에만 삭제와 삽입을 제공한다. 즉, 중간에 요소를 삽입하고 삭제하는 작업이 없다는 보장이 있기 때문에 일반 List보다 훨씬 빠른 처리가 가능해진다.

4. 정답 코드

class Solution {
    fun solution(queue1: IntArray, queue2: IntArray): Long {
        var answer: Long = 0
        
        var dq1 = ArrayDeque<Long>()
        var dq2 = ArrayDeque<Long>()
        
        queue1.forEach {
            dq1.add(it.toLong())
        }
        
        queue2.forEach {
            dq2.add(it.toLong())
        }
        
        var sumOfQueue1: Long = dq1.sum()
        var sumOfQueue2: Long = dq2.sum()
        
        var limitLoopCount = queue1.size * 4
        
         while (answer <= limitLoopCount) {
             if(sumOfQueue1 == sumOfQueue2) {
                 return answer
             }
             
             ++answer 
             
             if(sumOfQueue1 < sumOfQueue2) {
                 var element = dq2.first()
                 dq1.add(element)
                 dq2.removeFirst()
                 sumOfQueue1 += element
                 sumOfQueue2 -= element
                    
             } else {
                 var element = dq1.first()
                 dq2.add(element)
                 dq1.removeFirst()
                 sumOfQueue2 += element
                 sumOfQueue1 -= element
             }
        } 
        
        return -1
    }
}

이번 문제 풀면서 진짜 오랜 시간동안 '맞왜틀'을 외쳤는데,
덱(Deque)도 써보고, 갱장히 괴롭고 재미있었다......