[프로그래머스] 두 큐 합 같게 만들기

프로그래머스

2019 KAKAO TECH  INTERNSHIP

 

프로그래머스

두 큐 합 같게 만들기

 

문제 정리

1. 길이가 같은 두개의 큐가 주어진다.
2. 하나의 큐를 골라 원소를 추출(pop) 추출된 원소를 다른 큐에 집어 넣는 작업을 통해서 각 큐의 원소 합이 같도록 만들려고 한다.
3. 이떄 필요한 작업의 최소 횟수를 구하는 문제 한번에 pop과 한번의 insert를 합쳐서 작업을 1회 수행으로 간주
4. 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우는 -1 리턴

 

 

시작하기 전 접근 방법

1. 매개변수로 주어지는 배열을 저장할 2개에 queue를 만들고 각 queue에 들어있는 원소의 합을 저장할 sum 변수를 2개 만든다.
2. 배열에 있는 원소를 queue에 저장하며 queue에 들어있는 원소에 합을 구한다.
3. while문을 통하여 sum1과sum2가 같아질 때까지 반복문을 진행한다.
4. 각 queue에 대한 sum 값을 비교하여 sum이 작은 곳에서 큰 곳으로 queue에 값을 꺼내어 옮긴다.
5. 값을 꺼내오 옮겨 저장할 때마다 answer 값을 1씩 증가 시킨다.
6. queue에 원소가 다 꺼내질 때까지 같아지는 구간이 없다면 -1을 return한다.

 

테스트 예제 값

 

 

 

1. 매개변수로 주어진 배열을 queue에 저장하는 것과 각 queue에 들어 있는 원소에 합을 구한다.
배열에 있는 값에 타입은 int형이지만 queue에 들어갈 타입은 long 이기 때문에 각제 타입 캐스팅을 하여 타입을 맞춘다.

long sum1 = 0;
long sum2 = 0;
Queue<Long> que1 = new LinkedList<>();
Queue<Long> que2 = new LinkedList<>();

	for (int i = 0; i < queue1.length; i++) {
		que1.add((long) queue1[i]);
		sum1 += queue1[i];
		que2.add((long) queue2[i]);
		sum2 += queue2[i];
	}

 

 

2. queue에 들어 있는 원소에 핪이 같을 때까지 while문을 이용하여 반복한다.
3. 최대 이동 횟수는 (queue1+queue2)*2 만큼 가능하다. 하지만 queue1과 queue2는 크기가 같기 때문에 한 queue에 대한 길이를 구한 후 *4를 이용하여 표현하며 3번 과정에서 계속된 무한 루프에 빠지지 않게 하기 위한 설정이다. 따라서 최대 횟수보다 많이 이동할 경우 구할 수 없는 상황이기 때문에 -1을 반환한다.
4. queue에 값이 존재할 때는 sum이 작은 곳에서 sum이 큰 곳으로 queue값을 옮겨 각 queue에 대한 sum을 계산한다.
5 옮길 때마다 answer을 1씩 증가하고 queue가 비어있기 전까지 반복한다.
6. queue가 다 비어 있을때까지 반복해도 같아지는 상황을 찾을 수 없다면 구할 수 없는 상황이기 때문에 -1을 리턴한다.

while (sum1 != sum2) {
	if (answer > queue1.length * 4)
		return -1;
	long index = 0;
	if (!(que1.isEmpty() || que2.isEmpty())) {
		if (sum1 > sum2) {
			index = que1.poll();
			que2.add(index);
			sum1 -= index;
			sum2 += index;
		} else if (sum1 < sum2) {
			index = que2.poll();
			que1.add(index);
			sum1 += index;
			sum2 -= index;
		}
		answer++;
	} else {
	return -1;
	}
}

 

 

 

실수한 부분

처음 코드를 작성하는 과정에서 해설에서 작성한 3번에 해당하는 무한루프에 빠지게 되는 상황을 고려하지 못했다.
고려하지 않고 같아지는 answer만 구할 경우 테스트코드 11번과 28번이 시간 초과라는 결과가 나왔다.
예를 들어 queue1[] = {1,4}와 queue2[] = {4,8} 같은 배열이 매개변수로 주어지면 무한루프에 빠지게 된다.
같아지는 상황 없이 둘중 하나에 queue 크기가 0이 되는 상황이 안나오기 때문에 같은 주기를 반복하여 무한루프에 걸리게 된다.
이부분을 고려하지 않고 작성하면 실패한 테스트 결과가 나온다...
이걸 해결하기 위해서 if(answer>queue1.length*4) return -1; 이 코드를 추가해줘야 한다.
최대 이동 횟수는 (queue1.length + queue2.length)*2 만큼 가능하다 queue1길이와 queue2길이는 같기 때문에 위 코드처럼 *4로 합친 것이다.
이처럼 예외가 발생할 수 있는 상황도 고려하여 무한 반복에 빠지는 결과를 막아야 하는 것도 고려해야 한다.

 

 

 

전체 코드

 

package practice;

import java.util.*;

class Solution {
	public int solution(int[] queue1, int[] queue2) {
		int answer = 0;
		long sum1 = 0;
		long sum2 = 0;
		Queue<Long> que1 = new LinkedList<>();
		Queue<Long> que2 = new LinkedList<>();

		for (int i = 0; i < queue1.length; i++) {
			que1.add((long) queue1[i]);
			sum1 += queue1[i];
			que2.add((long) queue2[i]);
			sum2 += queue2[i];
		}

		while (sum1 != sum2) {
			if (answer > queue1.length * 4)
				return -1;
			long index = 0;
			if (!(que1.isEmpty() || que2.isEmpty())) {
				if (sum1 > sum2) {
					index = que1.poll();
					que2.add(index);
					sum1 -= index;
					sum2 += index;
				} else if (sum1 < sum2) {
					index = que2.poll();
					que1.add(index);
					sum1 += index;
					sum2 -= index;
				}
				answer++;

			} else {
				return -1;
			}
		}
		return answer;

	}

}