[프로그래머스/자바] 두 큐 합 같게 만들기 풀이 - 2022 KAKAO TECH INTERNSHIP

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

프로그래머스

 

2022 KAKAO TECH INTERNSHIP

Level 2 문제다.

 

 

 

처음엔 int[]에 담겨있는 값을 실제 Queue에 담아 

dfs로 하나씩 빼고 저장하려고 했는데,

입출력 예시 #2와 같이 queue1에서 queue2으로부터 받은 원소를 다시 queue2로 보내는 경우는 해결하지 못했다.

 

그래서 투포인터를 이용해 구현했고,

입출력 예시 #2와 같은 상황을 처리하기 위해 queue1과 queue2의 값을 하나의 배열 arr에 순서대로 저장하고,

end 포인트를 뜻하는 p2가 arr배열의 크기를 넘는다면 p2를 0으로 설정했다.

 

arr 배열을 기준으로 포인터를 움직여 두 큐 합이 같은 경우의 최소 횟수를 반환하는데,

이 때 포인터는 0부터 차례대로 증가하므로

가장 처음으로 두 큐의 합이 같아질 때가 최소 횟수이다.

 

 

class Solution {

	static int solution(int[] queue1, int[] queue2) {
		int n = queue1.length;
		long sum1 = 0, sum2 = 0;
		long equal;
		int p1 = 0, p2 = n;
		int ans = 0;

		int[] arr = new int[n * 2];

		for(int i=0;i<n;i++) {
			sum1 += queue1[i];
			sum2 += queue2[i];

			arr[i] = queue1[i];
			arr[i + n] = queue2[i];
		}
		equal = (sum1 + sum2) / 2;
		
		while(p1 < 2 * n) {
			if(sum1 == equal)
				return ans;
			
			if(sum1 < sum2) {
				sum1 += arr[p2];
				sum2 -= arr[p2];
				p2 = p2 + 1 >= n * 2 ? 0 : p2 + 1;
			}
			else {
				sum2 += arr[p1];
				sum1 -= arr[p1];
				p1++;
			}
			ans++;
		}

		return -1;
	}
}