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

문제 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;  최종 값 출력
   }

 

 

[종료조건]

 

 

검색 실패일 경우에는 -1 을 출력하는데 언제를 검색 실패로 생각할 지 조건을 정해줘야 해요

"서로의 원소를 모두 교환해도 답이 나오지 않는다!" 가 포인트 인 것 같아요

그래서 원소 총 개수보다 연산이 + 1만 더 늘어나도 종료가 되게끔 설정해주면 됩니다

저는 넉넉잡아 *3을 해주었지만 두 큐길이의 합 + 1로 풀어도 정답입니다

* 원소 총 개수 = 두 큐 길이의 합 = queue1.length

종료조건	queue1.length * 3	queue1.length * 2 + 1
결과

 

 

 

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

프로그래머스

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *