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

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

프로그래머스

 

문제 풀이

이 문제 풀 때 애 먹었던 것

1. 시간초과
2. 최대 몇번 걸리는 것인지

이 2가지입니다. 처음에는 무한 루프로 돌면서 두 큐가 같은 값이 될 때까지 돌리니, 시간초과 에러가 났습니다. 

왜 시간초과가 날까... 무한루프 때문이겠거니... 그래서 최대로 계산을 몇번 할까를 생각했습니다.

제한사항을 보면, queue1과 queue2의 길이는 같고 최대 길이는 300,000 입니다.

그렇다면 queue1 길이 * 2 만큼 최대 계산을 할줄 알았는데, 아니였습니다. 그래도 계속 시간초과 에러가 있더군요..

혹시... Queue가 아닌 List를 썼기 때문일까... 해서 list를 queue로 바꿨더니 시간초과 에러는 더 이상 발생하지 않았습니다.

하지만 계속 1번을 틀리더군요.. 질문하기를 보니 최대 연산 값을 queue 길이 * 4로 잡아야한다더군요...? (이것에 대한 의견도 다양하고, 증명은 되지 않았습니다.)

어쨋든.. 연산 최대값을 늘려야하는구나.. 근데 4배인건 너무 긴거 아닌가... 조금만 늘리면 될 거 같은데... 하는 생각으로 1씩 증가시켜 봤습니다. 

그러니 딱 +3 하면 통과되더군요. 아직도 왜 이게 최대 값인지는 증명하지 못 하겠습니다.

 

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long q1 = 0, q2 = 0, sum = 0;
        Queue<Integer> qu1 = new LinkedList<>(), qu2 = new LinkedList<>();
        for (int i = 0; i < queue1.length; i++) {
            qu1.add(queue1[i]); qu2.add(queue2[i]);
            q1 += queue1[i]; q2 += queue2[i];
        }
        sum = q1 + q2;
        if (sum % 2 != 0) return -1;
        sum /= 2;
        for (int i = 0; i <= queue1.length*2+2; i++) {
            if (q1 == sum) return answer;
            if (q1 > q2) {
                q1 -= qu1.peek();
                q2 += qu1.peek();
                qu2.add(qu1.poll());
            } else {
                q1 += qu2.peek();
                q2 -= qu2.peek();
                qu1.add(qu2.poll());
            }
            answer++;
        }
        return -1;
    }
}

왜 list보다 queue가 빠를까 싶으시다면..!

 

https://gist.github.com/FedericoPonzi/8d5094dbae33cbb94536a73f62d1c1a0

Big O notation for java's collections

참고하시길 바랍니다.. 

안녕히계세요뿅