99클럽 코테 스터디 8일차 TIL + 베스트앨범(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 구현

   - 큐

공부한 내용 본인의 언어로 정리하기

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

큐를 사용하는 구현 문제를 풀었다.

마지막에 몇 번 까지 큐의 원소를 옮길 지 고민하는게 어려웠다.

 

풀이 과정은 다음과 같다.

0. 만약 모든 원소들의 합이 홀수라면 -1을 반환한다.

1 - 1. 2개의 큐에 각각의 원소들을 담는다

1 - 2. 2개의 큐의 원소들의 합을 각각 구한다

2. 두개의 큐 중 합이 큰 큐에서 작은 큐로 원소를 옮긴다

3. 이를 전체 원소가 n개라면 3n - 2번 반복한다.

3n - 2번 반복하는 이유는 큐에 원소를 하나만 남기고 다른 큐에 옮기는데 n - 1번의 연산이 필요하고

이후 2n - 1개의 원소가 있는 큐에 원소가 하나만 남을 때 까지 옮기는게 2n - 1번으로

총 3n - 2번 반복하면 가능한 모든 경우의 수를 알 수 있다.

 

 

풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    public int solution(int[] queue1, int[] queue2) {
        
        long sum = 0, que1Sum = 0, que2Sum = 0;
        int length = queue1.length;
        
        Deque<Integer> que1 = new ArrayDeque<>();
        Deque<Integer> que2 = new ArrayDeque<>();
        
        for (int i = 0; i < length; i++) {
            sum += queue1[i];
            que1Sum += queue1[i];
            que1.addLast(queue1[i]);
            
            sum += queue2[i];
            que2Sum += queue2[i];
            que2.addLast(queue2[i]);
        }
        
        if (sum % 2 != 0) return -1;
        
        for (int i = 0; i < length * 3 - 2; i++) {
            
            if (que1Sum == que2Sum) return i;
            
            if (que1Sum > que2Sum) {
                int element = que1.pollFirst();
                // System.out.println("que1 : " + element);
                que2Sum += element;
                que1Sum -= element;
                que2.addLast(element);
            } else {
                int element = que2.pollFirst();
                // System.out.println("que2 : " + element);
                que1Sum += element;
                que2Sum -= element;
                que1.addLast(element);
            }
            
        }
        return -1;
    }
}

 내일 학습할 것은 무엇인지

내일은 운영체제에서 프로세스와 스레드 관련 단원을 공부할 예정이다.