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

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

프로그래머스

 

 

 

 

 

문제

• 길이가 같은 두 개의 큐가 주어진다.
• 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 한다.
• 이때 필요한 작업의 최소 횟수를 구하기
  • 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주
  • 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return

 

제한사항

• 길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어진다.
• 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000
• 1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9

 

 

 

 

 

풀이

전체 로직

1. queue1과 queue2 각 큐의  원소 합을 구한다.

2. 원소 합을 비교해서 합이 큰 큐에서 원소를 빼고, 합이 작은 큐에 넣는다.

3. 같을 때까지 반복한다.

 

 

 

• 자료구조 : Queue

 문제에서는 매개변수로 두 개의 큐가 정수 배열로 주어지지만, 원소를 pop하고 insert하는 작업을 해야 하기 때문에 각 배열에 있는 원소들을 큐를 생성해 넣어준다.

 

 

• 원소 합 구하기, 갱신하기

 매번 큐 전체를 순회하며 원소의 총합을 구하는 것은 비효율적이므로, 따로 queue1과 queue2 의 원소 합을 변수로 두어 갱신해준다. 문제의 제한 사항을 보면 1 ≤ 원소 ≤ 10^9 이므로, 총 합이 int의 범위(약 21억)을 넘을 수 있으므로 long으로 선언한다.

 

 

• 불가능한 경우 판단하기

1. 작업을 수행하기 전부터 각 큐의 원소 합이 같을 수 없는 경우가 있다. 두 큐에 있는 원소 합이 홀수인 경우에는 나누기 2를 했을 때 정수가 아니므로 불가능하다.

 

 

2. 일정 횟수를 넘어가게 되는 경우이다. 횟수를 지정하지 않으면 무한루프가 될 것이다. (예시 1)

 

처음에 나름 규칙을 찾아 작업 횟수가 queue1.length + queue2.length를 넘어가면 -1을 리턴해 종료하도록 했다. 하지만 테스트케이스 30개중 1번 테스트 케이스만 통과하지 못했다.

 

문제 내 질문 게시판을 보다가 작업 횟수가  queue1.length + queue2.length를 넘어가서 두 큐의 합이 같게 되는 경우가 있는 반례를 발견했다. (예시 2) 그래서 넉넉하게 (queue1.length + queue2.length) * 2를 넘어가면 -1을 리턴해 종료하도록 했다.

 

 

 

예시1)

• queue1 = [1, 1], queue2 = [1, 5]

→  [1, 1, 1], [5] → [1, 1, 1, 5], [ ] → [1, 1, 5], [1] → [1, 5], [1, 1]

 

=> 4번만에 queue1과 queue2가 바뀌어 돌아와서 결국 무한루프가 됨

 

 

예시2)

• queue1 = [1, 1, 1, 1, 1, 1] , queue2 = [ 1, 1, 1, 1, 11, 1]

 

=> 15번만에 두 큐의 합이 같게 만들 수 있다. 

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> que1 = new LinkedList<>();
        Queue<Integer> que2 = new LinkedList<>();
        
        //큐에 원소 넣기
        long sum1 = 0; //1의 총합
        for(int n : queue1) {
            que1.add(n);
            sum1 += n;
        }
        
        long sum2 = 0; //1의 총합
        for(int n : queue2) {
            que2.add(n);
            sum2 += n;
        }
        
        //합이 홀수면 불가능
        if((sum1 + sum2) % 2 == 1) {
            return -1;
        }
        
        //계산
        int length = (queue1.length + queue2.length) * 2; //두 큐의 길이 합
        
        int answer = 0;
        while(true) {
            //종료 조건
            if(answer >= length) return -1; //길이 넘어가면 불가능
            if(sum1 == sum2) break; //각 큐의 원소 합 같음
            
            //합 비교 후, 큰 쪽에서 빼서 작은 쪽에서 넣기
            if(sum1 > sum2) {
                int p = que1.poll();
                sum1 -= p;
                sum2 += p;
                que2.add(p);
            } else {
                int p = que2.poll();
                sum2 -= p;
                sum1 += p;
                que1.add(p);
            }
            
            answer++;
        }
        
        return answer;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점