728x90
문제
https://school.programmers.co.kr/learn/courses/30/lessons/118667
해설
두 큐를 한 요소씩 이동하며 같은 합이 나오는 최소한의 횟수를 구하는 문제입니다.
큐의 특징상 들어가고 나오는 순서가 정해져있어 임의의 요소를 옮길 수 없습니다. 따라서 반복을 통해 결과를 도출해야합니다.
두 큐의 합이 같아지도록 만들기 위해 반복되는 내부에서는 큐의 합이 더 큰 쪽에서 작은 쪽으로 한 값씩 이동하며 비교해 줍니다.
반복을 멈추는 조건으로는 두 큐의 합이 같거나, 모든 가능성을 파악한다, 2가지로 정리해 볼 수 있습니다.
두 큐를 서로 이동 할 때 처음 상태로 돌아가기 위해서는 최대 (큐1의 길이 + 큐2의 길이) *2만큼 필요합니다.
위 정보들을 정리해 답을 구해낼 수 있습니다.
주의점
- 두 큐의 합이 같으려면 입력으로 주어진 값들의 합이 짝수여야 가능하고 홀수라면 -1로 return한다
- 두 큐를 서로 이동할 때 처음 상태로 다시 돌아가는 최악의 횟수는 (큐1의 길이 + 큐2의 길이) *2 가 된다.
- 연산중 값이 int범위 이상으로 커질 수 있어 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,sum2=0;
for(int i=0;i<queue1.length;i++){
q1.offer(queue1[i]);
sum1 += queue1[i];
q2.offer(queue2[i]);
sum2 += queue2[i];
}
//총합이 홀수인 경우 같게 만들기 불가능
if((sum1+sum2)%2==1)return -1;
int move=0;
// 두 합이 같거나 모든 경우를 확인한 경우 while탈출
while(sum1!=sum2 && answer<=4*queue1.length){
if(sum1>sum2){
move = q1.poll();
sum1 -= move;
sum2 += move;
q2.offer(move);
}else if(sum2>sum1){
move = q2.poll();
sum2 -= move;
sum1 += move;
q1.offer(move);
}
answer++;
}
// 모든 경우를 보았지만 실패한 경우
if(sum1!=sum2)return -1;
return answer;
}
}
728x90
'[IT] 코딩테스트 > [문제 및 풀이] 프로그래머스' 카테고리의 다른 글
[프로그래머스] PCCP 기출문제 2번 (석유 시추) / 자바(Java) (0) | 2024.01.03 |
---|---|
[프로그래머스] 주차 요금 계산 / 자바(Java) (0) | 2023.11.07 |
[프로그래머스] 푸드 파이트 대회 / 자바(Java) (1) | 2023.11.02 |
[프로그래머스] 성격 유형 검사하기 / 자바(Java) (1) | 2023.11.01 |
[프로그래머스] 이모티콘 할인행사 / 자바(Java) (0) | 2023.10.31 |