프로그래머스 lv2 - 두 큐 합 같게 만들기 (자바) [2022 KAKAO TECH INTERNSHIP]

문제

---

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

풀이

---

두 가지 풀이법 존재 : 투 포인터, 그리디

투포인터

• 큐1과 큐2를 붙여서 하나의 1차원 배열로 만든다.
  • 큐1에서 팝, 인서트 작업을 하는 것 → 큐 1의 맨 앞을 큐2의 맨 뒤로 붙임
  • 큐2에서 팝, 인서트 작업을 하는 것 → 큐 2의 맨 앞을 큐1의 맨 뒤로 붙임
  • 이런 구조기 때문에 두 큐를 합쳐서 1차원 배열로 만들고 투포인터로 접근한다.
• mid = (큐1의 합 + 큐2의 합) / 2
• 큐1의 맨 앞과 큐2의 맨 뒤를 st, end 포인터로 잡고 투포인터 알고리즘을 진행한다.
  1. st ~ end의 원소의 합 < mid 인 경우 end++하고 합에 end 위치를 추가
  2. st ~ end의 원소의 합 > mid 인 경우 합에서 st 위치를 빼주고 st++
  3. st ~ end의 원소의 합 = mid인 경우 종료
     -> 제일 먼저 찾는 경우가 가장 이동 횟수가 적은 것이므로 정답인 최소 이동횟수가 됨
  4. 만약 mid를 찾지 못하면 쭉 진행하다가 st가 배열의 끝지점을 벗어나고 end가 배열의 끝지점에 위치하면 종료

그리디
sum = q1의 합 + q2의 합

• sum/2 보다 s1이 크다면 queue1에서 queue2로 옮기고, sum/2 보다 s2가 크다면 queue2에서 queue1으로 옮긴다는 규칙을 만들어보면 어떨까?
  • 그리디적 사고방식
• 최악의 경우 queue1과 queue2의 값들을 서로 전부 교환하는 경우 대략 길이의 2배만큼 진행한다.
  • queue1 → queue2로 이동한 횟수와
    queue2 → queue1로 이동한 횟수가 각각 처음 큐 길이의 2배만큼 진행되면 모두 봤다고 판단

코드

---

투포인터 사용

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        int[] q = new int[queue1.length + queue2.length];
        for (int i = 0; i < queue1.length; i++) {
            q[i] = queue1[i];
            q[i + queue1.length] = queue2[i];
        }

        int l = 0;
        int r = queue1.length;
        long sum = Arrays.stream(queue1).sum(); // q1 총합
        long sum2 = Arrays.stream(queue2).sum(); // q2 총 합
        long mid = (sum + sum2) / 2; // 각 큐의 원소 합이 되어야 할 값
        System.out.println(mid);
        while (l < r) {
            if (r < q.length && sum < mid)
                sum += q[r++];
            else if (sum == mid)
                return answer;
            else
                sum -= q[l++];
            answer++;
        }

        return -1;
    }
}

그리디 활용

import java.util.*;
class Solution {
    public int solution(int[] queue1, int[] queue2) {
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        long s1 = 0, s2 = 0, sum;
        for (int tmp : queue1) { q1.add(tmp); s1 += tmp; }
        for (int tmp : queue2) { q2.add(tmp); s2 += tmp; }
        sum = s1 + s2;
        if (sum % 2 == 1) return -1;
        sum /= 2;

        int p1 = 0, p2 = 0, limit = queue1.length * 2;
        while (p1 <= limit && p2 <= limit) {
            if (s1 == sum) return p1 + p2;
            if (s1 > sum) {
                s1 -= q1.peek();
                s2 += q1.peek();
                q2.add(q1.poll());
                p1++;
            } else {
                s2 -= q2.peek();
                s1 += q2.peek();
                q1.add(q2.poll());
                p2++;
            }
        }

        return -1;
    }
}