[프로그래머스] Lv.2 두 큐 합 같게 만들기 JAVA 풀이

Programmers/Lv.2

[프로그래머스] Lv.2 두 큐 합 같게 만들기 JAVA 풀이

Poorm 푸름 2023. 10. 10. 13:40

문제 Lv.2 두 큐 합 같게 만들기

: 길이가 같은 두 개의 큐

: 하나의 큐를 골라 원소를 추출(pop)하고 추출된 원소를 다른 큐에 집어넣는(insert) 작업

: 각 큐의 원소 합이 같도록 만드는 최소의 횟수 출력
어떤 방법으로도 같을 수 없다면 -1 출력

: 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주

: 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000

1 ≤ queue1의 원소, queue2의 원소 ≤ 109

주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요

: 입력 예

queue1 = [3, 2, 7, 2]

queue2 = [4, 6, 5, 1]

출력 예
result = 2

[코드]

import java.util.*;
class Solution {
    public long sum(int[] arr) {
        long a = 0;
        for(int i = 0; i < arr.length; i++) 
        {
            a += (long) arr[i];
        }
        return a;
    }
    public int solution(int[] queue1, int[] queue2) {
        
        int answer = 0;
        long sum_q1 = sum(queue1);
        long sum_q2 = sum(queue2);
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>(); 
        
        
        for(int i = 0; i < queue1.length; i++) {
            q1.add(queue1[i]);            
            q2.add(queue2[i]);
        }
        
        while(sum_q1 != sum_q2) {
            if(answer > queue1.length * 3)
                return -1;
            
            int add_num = 0;
            
            if(sum_q1 < sum_q2) {
                add_num = q2.poll();
                q1.add(add_num);
                sum_q1 += (long) add_num;
                sum_q2 -= (long) add_num;
            }
            
            else if(sum_q1 > sum_q2) {
                add_num = q1.poll();
                q2.add(add_num);
                sum_q1 -= (long) add_num;
                sum_q2 += (long) add_num;
            }
            
            else return answer;
            
            answer++;
            
        }
        return answer;
    }
}

: public long sum(int[] arr) { 각 큐의 합을 구하기 위해 설정
        long a = 0; long은 정수형 타입에서 가장 큰 타입
        for(int i = 0; i < arr.length; i++) 입력받은 배열만큼만 반복
        {
            a += (long) arr[i]; a는 arr의 합을 담은 것이다
        }
        return a; 총 합 리턴
    }

: public int solution(int[] queue1, int[] queue2) { main 실행

        int answer = 0; answer 초기화
        long sum_q1 = sum(queue1); 입력 queue1 배열의 총 합
        long sum_q2 = sum(queue2); 입력 queue2 배열의 총 합

        Queue<Integer> q1 = new LinkedList<>(); 큐1 설정
        Queue<Integer> q2 = new LinkedList<>(); 큐2 설정


        for(int i = 0; i < queue1.length; i++) { 큐1이나 큐2나 길이 같아서 아무거나 써도 상관없다
            q1.add(queue1[i]); 큐 q1 에 입력받은 배열 queue1의 데이터 넣기
            q2.add(queue2[i]); 큐 q2 에 입력받은 배열 queue2의 데이터 넣기
        }

        while(sum_q1 != sum_q2) { queue1 총 합 != queue2 총 합
            if(answer > queue1.length * 3) 대략적으로 잡은 숫자 (2로 하면 테스트 중 1개 실패)
아무리 돌려도 정확히 같게 나누어 떨어지지 않으면 answer가 계속 올라간다
                return -1; 대략 큐길이의 3배 만큼 돌아가도 답이 안나오면 구할 수 없는 문제라 -1 출력

            int add_num = 0; 추가해줄 숫자들 add_num 이라 설정

            if(sum_q1 < sum_q2) { queue1 총 합 < queue2 총 합
                add_num = q2.poll(); 추가할 숫자는 큐 q2에서 뺀 것
                q1.add(add_num); 합이 작은 큐 q1 에 원소 추가
                sum_q1 += (long) add_num; queue1 총 합 갱신
                sum_q2 -= (long) add_num; queue1 총 합 갱신
            }

            else if(sum_q1 > sum_q2) { queue1 총 합 > queue2 총 합
                add_num = q1.poll(); 추가할 숫자는 큐 q1에서 뺀 것
                q2.add(add_num); 합이 작은 큐 q2 에 원소 추가
                sum_q1 -= (long) add_num; queue1 총 합 갱신
                sum_q2 += (long) add_num; queue1 총 합 갱신
            }

            else return answer; queue1 총 합 = queue2 총 합 일 때, answer 값 출력

            answer++; 위와 같이 add_num 추가할 때마다 answer 1씩 카운트하기

        }
        return answer; 최종 값 출력
}