99클럽 코테 스터디 8일차 TIL / [프로그래머스] 두 큐 합 같게 만들기

오늘의 학습 키워드

---

Queue

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 두 큐 합 같게 만들기
• 난이도: Lv2

풀이

---

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum1 = 0, sum2 = 0;
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        
        for(int i=0; i<queue1.length; i++) {
            sum1 += queue1[i];
            q1.offer(queue1[i]);
        }
        
        for(int i=0; i<queue2.length; i++) {
            sum2 += queue2[i];
            q2.offer(queue2[i]);
        }
        
        while(answer <= 3 * queue1.length - 3) {
            if(sum1 == sum2) {
                return answer;
            }
            
            if(sum1 < sum2) {
                int element = q2.poll();
                q1.offer(element);
                sum1 += element;
                sum2 -= element;
            } else {
                int element = q1.poll();
                q2.offer(element);
                sum2 += element;
                sum1 -= element;
            }
            
            answer++;
        }
        
        return -1;
    }
}

접근

• 우선 각 큐의 원소 합이 같게 만드는 최소 작업 횟수를 구하기 위해 queue1, queue2 자료구조를 만들었습니다.
• 그리고 반복문을 돌면서 queue1의 합 sum1, queue2의 합 sum2를 비교했습니다.
  • sum1 > sum2 인 경우
    • queue1의 원소를 poll, queue2에 offer
  • sum2 > sum1 인 경우
    • queue2의 원소를 poll, queue1에 offer
  • sum1 == sum2 인 경우
    • 작업 횟수 리턴
• 하지만 위 경우 무한 루프에 빠지는 케이스가 발생할 수 있기에 언제까지 반복을 할 것인지 고려해야 했습니다.
  • 저는 경계값을 3n-3으로 잡았는데, 그 이유는 다음과 같습니다.
    • 가장 많이 움직이는 경우 ⇒ 한 쪽 큐의 마지막 원소를 제외하고(마지막 원소까지 이동하면 swap 되는 경우가 생기므로) 모두 이동시키는 경우
      • ex) q1 = {3, 2, 7, 2}, q2 = {4, 6, 5, 1} 일 때 가장 많이 움직인 경우
        • q1 = {5}, q2 = {1, 3, 2, 7, 2, 4, 6} or q1 = {2, 4, 6, 5, 1, 3, 2}, q2 = {7}
      • 위 예시를 일반화시켜보면 다음과 같습니다.
        • q1의 모든 원소 1번 이동 ⇒ n
        • q2의 마지막 제외 원소 1번 이동 ⇒ n-1
        • q2에서 q1으로 이동된 원소 중 마지막 제외 원소 1번 이동(큐에 최소한 원소 1개는 존재해야 하므로) ⇒ (n-1) - 1
        • ⇒ n + (n-1) + ((n-1) - 1) = 3n-3

소요 시간

30분

회고

---

이런 문제에 있어서 가장 중요한 것은 명확한 경계값 설정임을 느낄 수 있었습니다.