프로그래머스: 두 큐 합 같게 만들기 - javascript(시간복잡도 고려하는 구현문제)

문제 출처 

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

프로그래머스

문제 풀이 힌트 

이런 문제가 네이버의 1번으로 나올 수 있다.

max값을 설정하면서 N값을 제한하는 생각을 할 수 있느냐,

어떻게 하면 시간 복잡도를 줄일 수 있는가가 관건이 된다.

 

그 작은 차이가 합/불을 결정한다. 

 

내 코드가 무조건적으로 바꾸면서 시간 초과를 방지하는 것보다는, 

어떤 방식으로 시간 초과가 나지 않는지 생각해본다. 

01. 최대 시간을 제한 

02. 삽입과 삭제의 방식이 아닌, point로 idx를 지정하면서 총 합에서 빼고 더하는 것을 생각

문제 풀이 코드 

function solution(queue1, queue2) {
    let answer = 0; // 정답 변수 초기화
    const max = queue1.length * 2; // 최대 반복 횟수 설정
    let value = queue1.reduce((acc, cur, idx) => acc + cur - queue2[idx], 0) / 2; // 초기값 설정

    let [i, j] = [0, 0]; // 두 큐의 현재 인덱스 설정

    while (value !== 0 && answer < max * 2) { // 값이 0이 아니고 최대 반복 횟수를 넘지 않을 때까지 반복
        if (value > 0) { // 값이 양수일 때
            const v = queue1[i]; // 현재 큐1의 요소 가져오기
            i++; // 인덱스 증가
            value -= v; // 값 업데이트
            queue2.push(v); // 큐2에 요소 추가
        } else { // 값이 음수일 때
            const v = queue2[j]; // 현재 큐2의 요소 가져오기
            j++; // 인덱스 증가
            value += v; // 값 업데이트
            queue1.push(v); // 큐1에 요소 추가
        }
        answer++; // 반복 횟수 증가
    }

    return value !== 0 ? -1 : answer; // 값이 0이 아니면 -1을, 그렇지 않으면 반복 횟수를 반환
}

Only 풀이 코드 

function solution(queue1, queue2) {
    let answer = 0
    const max = queue1.length*2
    let value = queue1.reduce((acc,cur,idx)=>acc+cur-queue2[idx],0)/2
    let [i,j] = [0,0]
    while(value !== 0 && answer < max*2){
        if(value > 0){
            const v = queue1[i]
            i++
            value -= v
            queue2.push(v)
        }else{
            const v = queue2[j]
            j++
            value += v
            queue1.push(v)
        }
        answer++
    }
    return value !== 0 ? -1 : answer
}

 

알고가는 ppoint

01. 왜 answer++ 이 안되고, -1값이 return 됐는가?

function solution(queue1, queue2) {
    let answer = 0;
  while(queue1.length && queue2.length){
    let sum1 = queue1.reduce((a,b) => a+b,0); 
    let sum2 = queue2.reduce((a,b) => a+b,0);
      if(sum1 === sum2){
          return answer; 
      }else if(sum1 < sum2){
          queue2.push(queue1.shift()); 
      }else{
          queue1.push(queue2.shift()); 
      }
      answer++; 
  }
        return -1; 
}

=> 의심1. 반복문의 조건이 잘못됐는가? 

=> 아님 sum1과 sum2의 부등호를 반대로 함. 

function solution(queue1, queue2) {
    let answer = 0;
  while(queue1.length >0 && queue2.length > 0){
    let sum1 = queue1.reduce((a,b) => a+b,0); 
    let sum2 = queue2.reduce((a,b) => a+b,0);
      if(sum1 === sum2){
          return answer; 
      }else if(sum1 < sum2){
          queue1.push(queue2.shift()); 
      }else{
          queue2.push(queue1.shift()); 
      }
      answer++; 
  }
        return -1; 
}

 

02. queue의 시간 초과 

input의 값이 컸다. 그래서 하나씩 배열 앞에서 빼고, 배열 뒤에다 넣어주면 

시간 복잡도가 

You

제한사항이 아래와 같아. 시간초과가 일어날까?

1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000

1 ≤ queue1의 원소, queue2의 원소 ≤ 10^9 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.

 

ChatGPT

 

주어진 제한 사항을 고려할 때, 시간 초과가 발생할 가능성이 있습니다. 주요 이유는 다음과 같습니다:

1. 입력 크기가 최대 300,000이며, 각 큐의 길이가 최대 300,000일 때, 전체 요소의 수는 최대 600,000입니다. 이는 큰 입력이므로 처리 시간이 상당할 수 있습니다.
2. 각 반복에서 reduce() 함수를 사용하여 큐의 합계를 계산합니다. 이는 각 큐의 길이에 비례하여 시간이 걸리므로, 시간 복잡도가 O(n)입니다. 하지만 각 큐의 원소가 최대 10^9로 제한되어 있으므로 합계가 매우 커질 수 있습니다. 이 경우 산술 오버플로우가 발생할 수 있습니다.
3. 최악의 경우에는 한 큐에서 요소를 다른 큐로 이동할 때마다 배열을 재배열해야 하므로, 이러한 이동 작업도 추가적인 시간이 소요될 수 있습니다.

이러한 이유로 큰 입력에 대해 시간 초과가 발생할 수 있습니다. 최대한 효율적인 알고리즘을 고려하여 개선해야 합니다. 가능한 경우 산술 오버플로우를 방지하기 위해 long 형식을 사용하는 것이 좋습니다.

 

You

시간 복잡도가 On일때 input의 N값으로 어느정도까지가 괜찮은지 대략으로 말해줘

 

ChatGPT

ChatGPT

시간 복잡도가 O(n)일 때, 일반적으로는 N 값이 몇 천에서 몇 십만 정도일 때 괜찮은 성능을 보입니다. 하지만 컴퓨터의 성능, 입력 요소의 자료형 및 값 범위, 코드의 구현 방식 등에 따라 다를 수 있습니다.

일반적으로, 입력 크기가 몇 천 정도일 때는 대부분의 컴퓨터에서 합리적인 실행 시간을 보입니다. 하지만 몇 십만 이상의 큰 입력 크기일 때는 실행 시간이 늘어날 수 있으며, 이는 알고리즘의 효율성과 함께 고려해야 할 사항입니다.