[프로그래머스] lv2 두 큐의 합 같게 만들기 (JAVA)
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/118667#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
2. 문제 풀이 겸 회고
더 큰 큐쪽에서 숫자를 줘야 함 (반복적으로 하면 됨)
그래서 처음에 그냥 두 개 배열을 리스트에 담아서 add, remove(0) 해줬는데 값 구해줬는데 1번은 틀렸고, 24번 시초(시간 초과) 남.. 아놔....;;
그래서 아놔 뭐지 하면서 왕고민하다가.. 1번은 아예 값 자체가 틀려서.. 보니깐..
우선 스포먼저 하겠음
queue1: [1,1,1,1,1]
queue2: [1,1,1,9,1]
answer = 12;
숨_answer = -1;
예외 tc 돌려보삼..
틀린 사람덜..바보같이 나는 두 큐가 왔다 갔다 반복하다가 어차피 안될 경우 계속 무한 반복한다고 생각함
queue길이 *2 번 돌면 다시 제자리로 돌아올 것이라고 생각함! 저 TC 돌려보면 *3으로 해야할것을 알게 될꺼삼!
또한, 24...번..why 시초?..?????? list로 add, remove 랑 queue offer, poll 모야.. 시간 초과
결론: list remove 지우는 건 1이지만 앞으로 당겨줘야 돼서.. O(N)
queue는 어차피 맨뒤 삽입 맨 앞 삭제 -> O(1) ㅎㅎ...
진짜 둘이 비교해서 돌려보면 시간 차이 OMG~~~~~~
3. 코드
import java.util.*;
class Solution {
public int solution(int[] queue1, int[] queue2) {
//q1, q2에 sum1, sum2 구해주기 !
Queue<Integer> que1 = new LinkedList<>();
Queue<Integer> que2 = new LinkedList<>();
int len = queue1.length;
long sum1 = 0;
long sum2 = 0;
long target = (sum1 + sum2) / 2;
int answerCnt = 0;
for(int i=0;i<len;i++){
sum1 += queue1[i];
sum2 += queue2[i];
que1.offer(queue1[i]);
que2.offer(queue2[i]);
}
// q1, qu2중에서 큰쪽 -> 작은쪽 (숫자 보내기)
while(sum1 != sum2){
if(answerCnt >= len*3) return -1;
if(sum1 > sum2){
sum1 -= que1.peek();
que2.offer(que1.peek());
sum2 += que1.poll();
}else{
sum2 -= que2.peek();
que1.offer(que2.peek());
sum1 += que2.poll();
}
answerCnt++;
}
return answerCnt;
}
}