[ 문제 설명 ]
문제를 정리하면 다음과 같습니다.
- 문제 설명:
길이가 같은 두 개의 큐가 주어짐
> 하나의 큐를 골라 원소를 추출
> 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
> 그 작업을 통해 각 큐의 원소 합을 같게 만듬
> 이때, 필요한 작업의 최소 횟수를 구해라
> 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주
- 주의
> long type 권장
> 큐 길이 : 30만
> 원소 크기 : 10에 9승
[ 해결 방법 ]
* s1 = 배열1의 합 | s2 = 배열2의 합 | sum = 배열1,2의 합/2
* problem1,2 = pop(), insert() 한 횟수
1) 입력 받은 배열을 Queue 에 넣어준다.
2) 두 배열의 합이 만약 홀수이면 -1을 리턴해준다.
3) 합을 나누기 2를 해준다.
4) 반복문을 통해 아래의 내용을 비교해준다. ( 반복문은 problem1,2 가 큐의 길이가 두배가 되면 종료 )
- s1 이 sum 과 같으면 problem1 + problem2 를 리턴해준다.
- s1 이 sum 보다 크면,
s1 에 queue1 에서 peek() 한 값을 빼줌
s2 에는 더해줌
queue2 에 queue1 을 pop() 한 값을 poll() 해줌
problem1 을 하나 증가시킴
- 둘 다 아니면,
s2 에 queue2 에서 peek() 한 값을 빼줌
s1 에 더해줌
queue1 에 queue2를 pop()한 값을 poll() 해줌
problem2 를 하나 증가시팀
[ 소스 코드 ]
import java.util.ArrayDeque;
import java.util.Queue;
public class 큐문제 {
/**
- 문제 설명:
길이가 같은 두 개의 큐가 주어짐
> 하나의 큐를 골라 원소를 추출
> 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
> 그 작업을 통해 각 큐의 원소 합을 같게 만듬
> 이때, 필요한 작업의 최소 횟수를 구해라
> 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주
- 주의
> long type 권장
> 큐 길이 : 30만
> 원소 크기 : 10에 9승
**/
public static void main(String[] args) {
int[] queue1 = {3, 2, 7, 2};
int[] queue2 = {4, 6, 5, 1};
int solution = solution(queue1, queue2);
System.out.println(solution);
}
public static int solution(int[] queue1, int[] queue2) {
Queue<Integer> que1 = new ArrayDeque<>();
Queue<Integer> que2 = new ArrayDeque<>();
long s1 = 0, s2 = 0, sum = 0;
for (int i = 0; i < queue1.length; i++) {
que1.add(queue1[i]);
s1 += queue1[i];
que2.add(queue2[i]);
s2 += queue2[i];
}
sum = s1 + s2;
// 홀수가 될 경우 풀 수 없음
if (sum % 2 == 1) return -1;
sum = sum/2;
int problem1 = 0;
int problem2 = 0;
int limit = queue1.length * 2;
while (problem1 <= limit && problem2 <= limit) {
if(s1 == sum) return problem1 + problem2;
else if(s1 > sum){
s1 -= que1.peek();
s2 += que1.peek();
que2.add(que1.poll());
problem1++;
}
else {
s1 += que2.peek();
s2 -= que2.peek();
que1.add(que2.poll());
problem2++;
}
}
return -1;
}
}