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

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

---

 

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

프로그래머스

 

 

 

두 큐의 합을 같게 해야한다. 어떻게 최소값을 구할 수 있을까? 

큐1의 합 = 큐2의 합이 되려면, 둘 중 합이 더 큰 쪽에서 작은 쪽으로 값을 옮겨준다. 

이것을 반복해준다. 

언제까지? 

-> 두 합이 같을 때, 

그런데 이렇게 하면 정답을 구할 수 없는 경우 무한반복이 되기 때문에, 다른 조건을 추가해주어야 한다. 

만약 두 큐의 값을 서로 바꾸어주는 과정을 반복했을 때, 두 큐의 값이 원상복구된다면 한 바퀴를 돌은 와중에도 정답을 구할 수 없었다는 것이 된다. 따라서 큐들이 원상복구되는데 걸리는 최악의 시간 (q1의 길이+q2의 길이)*2로 제한을 해주었다. 

-> 두 합이 같을 때, 

-> 반복횟수가 (q1의 길이+q2의 길이)*2이하일때 

 

 

 

코드

---

import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        int limit=(queue1.length +queue2.length)*2; //두 큐의 합만큼 순회하하면 더 이상 진행불가 

        long sum1= Arrays.stream(queue1).sum();
        long sum2= Arrays.stream(queue2).sum();
        long target= (sum1+sum2)/2;

        Queue<Integer> q1= new LinkedList<Integer>();
        Queue<Integer> q2= new LinkedList<>();

        for(int i=0;i<queue1.length;i++){
            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }


        while(sum1!=target && answer<=limit){
            int temp=0;
            if(sum1>sum2){
                temp = q1.poll();
                q2.add(temp);
                sum1-=temp;
                sum2+=temp;
            }
            else{
                temp = q2.poll();
                q1.add(temp);
                sum2-=temp;
                sum1+=temp;

            }
            answer++;
        }

        if(answer>limit)
            return -1;
        return answer;
    }
}

 

 

큐를 이용한 풀이! 

 

2. 오늘의 회고

---

 

• 자바는 큐를 선언할 때 편의성을 위해 LinkeList를 사용한다. 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL