[프로그래머스] 두 큐 합 같게 만들기 with JS

알고리즘 스프린트 3일차 - [프로그래머스] Lv 2. 두 큐 합 같게 만들기 (카카오 기출)

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

소요시간

30분

 

계획

수도 코드 진짜 못쓰네

 

계획 짜면서 while문 조건을 안일하게 생각했음. 저 부분만 제대로 고민했어도 5분은 더 줄일 수 있었다

코드 짜면서 변경 된 while문 : while(l <= r && r < 두 큐의 길이의 합) 

풀이

• 문제 범위가 어마어마 함, 따라서 단순히 pop하고 insert하는 문제는 아니다 라고 확신을 함
• 하나의 큐에서 빠진 것이 다른 큐에 뒤에 들어가기 때문에
• 두 큐를 이어 붙여서 하나의 배열로 만들고, 한 쪽 큐의 합을 구간합으로 접근함
  • 큐 하나당 길이가 4인 큐 두 개를 예시로 들면
  • 두 큐를 붙였을 때, 0~3 까지 인덱스가 앞 큐, 4~7 인덱스가 뒷 큐를 표현함
  • 앞 큐의 첫 원소의 인덱스 l = 0, 마지막 원소의 인덱스 r = 3 으로 두면
  • 뒷 큐에서 하나 빼서 앞 큐에 넣는 것을 r+1 로 표현 가능하고
  • 앞 큐에서 하나 빼서 뒷 큐에 넣는 것을 l+1 로 표현 가능하다
• 위 방법을 이용하면 logN으로 해결 가능
• 이 방법을 고안하게 된 근거
  • 두 큐를 합친 배열에서 앞 큐의 범위를 인덱스를 통해 표현해주면 범위를 벗어난 배열의 나머지 부분은 자동으로 뒷 큐를 표현해준다

결과

코드

function solution(queue1, queue2) {
    var answer = -1;
    let sum = 0;
    let sumFront = 0;
    let sumQueue = queue1.concat(queue2);
    for (let i = 0; i < queue1.length; i++){
        sum += queue1[i] + queue2[i]
        sumFront += queue1[i];
    }
    
    let half = sum/2;
    let l = 0;
    let r = queue1.length - 1;
    let count = 0;
    
    while(l <= r && r < sumQueue.length){
        if (sumFront > half){
            sumFront -= sumQueue[l]
            l += 1;
        }
        else if(sumFront < half){
            r += 1;
            sumFront += sumQueue[r]
        }
        else{
            answer = count;
            break;
        }
        count++;
    }
    return answer;
}

 

마치며

오늘은 문제를 제대로 이해하기 위해 세 번 읽었다. 계획도 최대한 꼼꼼히 짜려고 노력했지만 실수한 부분이 있어서 엣지 케이스 두 개가 통과가 안됐다. while문 종료 조건을 더 정확하게 계획해야겠다! 그래도 접근방법은 잘 세운것 같아서 뿌듯하다