1. 문제 설명
2. 접근 방식
KEY WORD
: GREEDY
- 문제 설명 그대로 Queue 두 개를 만든다.
- 총합이 큰 쪽의 queue.peek()을 poll 해서 다른 쪽 큐에 추가한다.
- 2번 종료 후 두 큐의 총합이 같은지 검사한다.
- 만약 같으면, 2번을 행한 횟수를 출력한다. 만약
두 큐의 총 길이 + 1
만큼 해도 두 큐의 합이 같지 않으면 -1을 출력하고 종료 한다.
두 큐의 총 길이 + 1 만큼 반복해야 하는 이유는 뒤에서 설명.
3. 코드 분석
import java.io.*;
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
ArrayDeque<Integer> a = new ArrayDeque<>();
ArrayDeque<Integer> b = new ArrayDeque<>();
// sum == 각 큐의 합, cnt == 작업 횟수
long sumA = 0;
long sumB = 0;
int cnt = 0;
for(int i = 0; i < queue1.length; i++){
a.add(queue1[i]);
b.add(queue2[i]);
sumA += queue1[i];
sumB += queue2[i];
}
if((sumA+sumB)%2 == 1) return -1;
// 그 때 그 때 매번 sum을 구하지 말고, 하나 구해놓고 +,-로 조정한다.
while(sumA != sumB){
// 기저 조건
if(cnt > (queue1.length + queue2.length)+1) {
cnt = -1;
break;
}
if(sumA > sumB){
int now = a.poll();
sumA -= now;
sumB += now;
b.add(now);
}
else if(sumB > sumA){
int now = b.poll();
sumB -= now;
sumA += now;
a.add(now);
}
cnt++;
}
return cnt;
}
}
4. 성장 하기
(1) 해당 문제에서 원소의 최대 크기는 10^9이었다. 따라서 총합을 구할 시, int형의 최대값인 21억을 넘을 수 있다.
sum의 자료형은 int가 아니라 Long으로 해야한다.
-> 해당 부분을 자주 간과해서, 맞는 코드를 작성하고도 해메는 경우가 많다. 자료형이 변수의 값을 감당할 수 있는지를 항상 체크하자.
(2) 반복문이 queue의 길이의 합 + 1
만큼 반복되어야 하는 이유
Input을 다음과 같이 넣어보자.
queue1 | queue2 | result |
---|---|---|
[3,3,3,3] | [3,3,27,3] | 9 |
해당 값이 서로 27로 일치하기 위해서는 9번의 움직임이 필요하다. 따라서 queue의 길이의 총합 보다 좀 더 넉넉히 가져가야 한다. 이것을 반례 전에 파악할 수 있는 방법이 있는지는 아직 잘 모르겠다.
다음에 코딩 테스트에서도 일부 틀릴 경우, 이러한 반례가 있을 경우를 대비해 반복문의 길이를 시간 초과가 안나는 선에서 넉넉히 가져가는 방법을 고려하자.
'알고리즘 > 문제 풀이' 카테고리의 다른 글
99클럽 코테 스터디 9일차 TIL + 백준 1927 최소힙 java (0) | 2024.07.30 |
---|---|
[백준] 1522 문자열 교환 풀이 java (0) | 2024.07.29 |
99클럽 코테 스터디 5일차 TIL + Programmers 베스트 앨범 (0) | 2024.07.27 |
99클럽 코테 스터디 4일차 TIL + Programmers 문자열 압축 (0) | 2024.07.25 |
[백준] 1806 부분합 풀이 java (0) | 2024.07.24 |