2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기 (JAVA)

❓ 문제 - 2022 KAKAO TECH INTERNSHIP 두 큐 합 같게 만들기- JAVA 풀이법

출처 

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

프로그래머스

 

 

📝 문제해결법

1. 문제

• 길이가 같은 두 큐가 있을 때 하나의 큐에서 원소를 추출(pop)하고 추출된 원소를 다른 큐에 집어 넣는(insert) 연산을 통해 두 큐의 합이 같도록 만들어야 한다.
• 이때 필요한 작업의 횟수를 구하는 것이 문제의 핵심이다.

2. 해결 방법

• 투포인터의 느낌으로 문제를 해결했다.
• 우선 두 개의 큐를 하나의 이어진 큐 형태로 만들고 모든 큐의 sum을 구한다.
• 그리고 첫 번째 큐의 합 sum2와 두 개를 이은 queue에 queue1 다음에 queue2가 오도록 한다.
• 그리고 queue에서 첫 번째 가리키는 부분을 start, queue1의 마지막 인덱스 부분을 end로 가리키게 한다.
• sum2의 값이 두 큐의 합의 반절보다 크다면 start 포인트를 +1 증가시키고, 두 큐의 합이 반절보다 작다면 end 포인트를 +1 증가시킨다. start와 end를 증가시킬 때마다 cnt를 1증가시킨다.
• 따라서 start와 end로 두 큐의 합의 반절 합인 구간을 구하고 그 때 이동시킨 cnt 값을 정답으로 출력한다.
• 하지만 end도 queue의 끝 인덱스까지 도착하고, start도 end의 값과 같아지면 -> 모두 다 탐색했는데 두 큐가 같아질 수 없으므로 -1을 출력하도록 한다.

3. 느낀점

• 실제 카카오 문제 풀면서 접근했던 방식인데 그 때는 두 개의 케이스에서 자꾸 통과를 못 했다..
• 알고보니 sum 값을 long 타입으로 했어야 했고! end부분을 접근할 때 queue 인덱스 이상의 값을 접근해서 arrayindex error가 나므로 이런 부분도 코드를 수정하니 잘 통과되었다.
• 다른 분들은 자료구조 큐 두 개 선언해서 문제에서 주어진대로 실제 구현해서 해결했던데.. 내 코드랑 다른 사람들 코드랑 돌려보니 나의 풀이가 압도적으로 빠르긴 했다..!

 

💻 소스코드 (JAVA)

// 2022 KAKAO TECH INTERNSHIP - 두 큐 합 같게 만들기
// 투포인터
class Solution {
    public static int[] queue;
    public static long sum;
    public int solution(int[] queue1, int[] queue2) {
        int answer = -1;
        long sum2 = 0;
        queue = new int[queue1.length + queue2.length];
        
        for(int i=0;i<queue1.length;i++){
            queue[i] = queue1[i];
            sum += queue1[i];
            sum2 += queue1[i];
        }
        
        for(int i=0;i<queue2.length;i++){
            queue[queue1.length+i] = queue2[i];
            sum += queue2[i];
        }
        sum /= 2;
        int start = 0;
        int cnt = 0;
        int end = queue1.length-1;
        outer: while(start < queue.length){
            while(end < queue.length){
            // start와 end로 표현하는 큐는 두 큐의 합의 반절과 같은 경우
                if(sum2 == sum){
                    answer = cnt;
                    break outer;
                    // start와 end로 표현하는 큐는 두 큐의 합의 반절보다 작은 경우
                } else if(sum2 < sum){
                    end++;
                    if(end == queue.length) break;
                    sum2 += queue[end];
                    cnt++;
                    continue;
                    // start와 end로 표현하는 큐는 두 큐의 합의 반절보다 큰 경우
                } else if(sum2 > sum){
                    sum2 -= queue[start];
                    break;
                }
            }
            // start와 end로 표현하는 큐는 두 큐의 합의 반절보다 작은 경우에 start를 1증가
            start = start+1;
            cnt++;
            if(start == end) {
                end = start+1;
                if(end == queue.length) break;
            }
        }
        
        return answer;
    }
}