두 큐 합 같게 만들기
문제 설명
첫 번째 사진에 너무 잘 설명이 되어있다..^^
2번째 예시로 설명해보자면
[1,2,1,2]와 [1,10,1,2]의 모든 원소의 합은 20이다. 그러므로 한 큐에 10이 되면 정답이다.
우선 q1과 q2중에 작은 값을 갖고있는 큐에게 큰 값을 갖고 있는 큐의 앞 수를 빼서 넣어준다.
이런식으로 q2에서 1과 10을 빼서 q1에 넣어주고 q1에서는 1,2,1,2,1(이 1은 q2에서 간 친구)를 q2에 넣어준다. 그럼 각 큐의 합은 10(sum/2)이 되기 때문에 그때의 교환 횟수(answer)을 반환해준다.
시행착오 및 문제 풀이
오답 풀이
-
for문을 통해 int배열 queue1과 queue2를 각 큐에 넣어준다. 동시에 각 큐의 합을 구해준다.
-
while문을 통해 각 큐의 값(sum1, sum2)이 전체 큐의 합(sum)/2과 같아지기 전까지 반복해준다.
2-1. q1의 합(sum1) q2보다 작다면
q2에서 원소 하나를 빼서 q1에 넣어준다.
sum1에 q2에서 뽑은 수를 더해주고, sum2에서는 빼준다.
q2에서 삭제하고 교환 횟수(answer)++2-2. q2의 합(sum2) q1보다 작다면
q1에서 원소 하나를 빼서 q2에 넣어준다.
sum2에 q1에서 뽑은 수를 더해주고, sum1에서는 빼준다.
q1에서 삭제하고 교환 횟수(answer)++ -
각 원소가 제자리에 돌아왔는데도 조건을 만족할 수 없다면 -1 반환
오답 코드
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int answer = 0;
//큐로 만들기
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
//합 구하기
int sum1 = 0;
int sum2 = 0;
for(int i=0; i<queue1.length; i++) {
q1.add(queue1[i]);
q2.add(queue2[i]);
sum1 += queue1[i];
sum2 += queue2[i];
}
int sum = sum1+sum2;
while(true) {
//원소의 합이 같다면
if(sum1 == (sum/2) && sum2 == (sum/2)) {
break;
}
//q1이 작다면 q2에서 넘기기
if(sum1 < sum/2) {
q1.add(q2.peek());
sum1 += q2.peek();
sum2 -= q2.peek();
q2.poll();
answer++;
}
//q2가 작다면 q1에서 넘기기
else if(sum2 < sum/2) {
q2.add(q1.peek());
sum2 += q1.peek();
sum1 -= q1.peek();
q1.poll();
answer++;
}
//각 큐의 합이 같아질 수 없으면 -1
if(answer >= queue1.length*2) {
answer = -1;
break;
}
}
return answer;
}
}뭐야? 제출했더니 73.3 나옴
아하 문제를 읽어보니 long형을 쓰라는 힌트 를 주셨네 ㅇㅋ~
그래서 long형으로 변환
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int answer = 0;
//큐로 만들기
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
//합 구하기
long sum1 = 0;
long sum2 = 0;
for(int i=0; i<queue1.length; i++) {
q1.add(queue1[i]);
q2.add(queue2[i]);
sum1 += queue1[i];
sum2 += queue2[i];
}
long sum = sum1+sum2;
while(true) {
//원소의 합이 같다면
if(sum1 == (sum/2) && sum2 == (sum/2)) {
break;
}
//q1이 작다면 q2에서 넘기기
if(sum1 < sum/2) {
q1.add(q2.peek());
sum1 += q2.peek();
sum2 -= q2.peek();
q2.poll();
answer++;
}
//q2가 작다면 q1에서 넘기기
else if(sum2 < sum/2) {
q2.add(q1.peek());
sum2 += q1.peek();
sum1 -= q1.peek();
q1.poll();
answer++;
}
//각 큐의 합이 같아질 수 없으면 -1
if(answer >= queue1.length*2) {
answer = -1;
break;
}
}
return answer;
}
}96.7 뭔데
왜 1번 테스트 통과 못하는데 왜.
그래서 1번 테스트가 무엇인지 알아봤다
입력값 〉 [1, 1, 1, 1], [1, 1, 7, 1]
기댓값 〉 9내가 실수한 부분 발견!
//각 큐의 합이 같아질 수 없으면 -1
if(answer >= queue1.length*2) {
answer = -1;
break;
}요기가 틀린 것이다...
난 단순하게 생각해서 q1이 q2에 다 가고, q2가 q1에게 다 가는 경우만 생각해서 길이*2라고 생각하고 풀었다.
하지만 위의 테스트같은 경우엔 내가 계산한 8이 초과해버렸다는......
더 차분하게 생각해보니 범위 설정을 잘못했더라
q1 = [A, B]
q2 = [C, D]
q1 → q2 (2번 이동)
A → q2로
B → q2로
q1: []
q2: [C, D, A, B]
q2 → q1 (2번 이동)
C → q1로
D → q1로
q1: [C, D]
q2: [A, B]
-> 로테이션
q1 → q2 (2번 이동)
C → q2로
D → q2로
q1: []
q2: [A, B, C, D]
q2 → q1 (2번 이동)
A → q1로
B → q1로
q1: [A, B]
q2: [C, D]
이렇게 4번 반복하면 원래의 자리로 돌아간다.
=> queue1.length*4
정답 코드
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
int answer = 0;
//큐로 만들기
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
//합 구하기
long sum1 = 0;
long sum2 = 0;
for(int i=0; i<queue1.length; i++) {
q1.add(queue1[i]);
q2.add(queue2[i]);
sum1 += queue1[i];
sum2 += queue2[i];
}
long sum = sum1+sum2;
while(true) {
//원소의 합이 같다면
if(sum1 == (sum/2) && sum2 == (sum/2)) {
break;
}
//q1이 작다면 q2에서 넘기기
if(sum1 < sum/2) {
q1.add(q2.peek());
sum1 += q2.peek();
sum2 -= q2.peek();
q2.poll();
answer++;
}
//q2가 작다면 q1에서 넘기기
else if(sum2 < sum/2) {
q2.add(q1.peek());
sum2 += q1.peek();
sum1 -= q1.peek();
q1.poll();
answer++;
}
//각 큐의 합이 같아질 수 없으면 -1
//모든 원소가 제자리로 돌아오는 경우 -> queue1.length*4
if(answer >= queue1.length*4) {
answer = -1;
break;
}
}
return answer;
}
}queue1로 한 이유는.. 딱히 없다 그냥 문제 풀다가 눈이 마주쳐서 사용함
간만에 내 스스로 풀었다ㅎ
