중첩반복문 알고리즘 질문드립니다!!


(dev_park) #1

안녕하세요 중첩 반복문 알고리즘 질문하나 드립니다.

문제
배열 [1, 2, 3, 4]
가 있다면 1+2+3+4 + 2+3+4 + 3+4 를 구하시오
인데

for(var i = 0; i < 4; i++){
for(var j = i+1; j < 4; j++){
console.log(i+’-’+j)
}
}

저는 위와같이 중첩반복문으로 풀어봤는데 만약 배열의 크기가 5000 이라고 하면
엄청 오랜시간이 걸리더라구요…
혹시 시간복잡도를 줄이고 효과적으로 해결할 수 있는 방법이 있을까 궁금합니다!


(Thomas) #2

저도 잘 모르지만. 앞에서 구한값을 다음 연산에 넘겨주는 식으로 반복문의 숫자를 줄일 수 있을 것 같습니다.


(name) #3

음… 값 * (i + 1)씩 한걸 다 더하면 되지 않을까요

예를들어
[1,3,5,9] 라고 할때

9+5+3+1
9+5+3
9+5
9
를 모두 더한 것을 구하는 것인데

1이 1개
3이 2개
5가 3개
9가 4개입니다.

그럼
1*1 + 3*2 + 5*3 + 9*4가 되겠네요.

이런식이면 반복문은 한개로 될거 같아요.

만약 1, 2, 3, 4와 같이 연속된 수이면
수학공식으로 딱 떨어져서 반복문으로 돌지않아도 될 것 같네요.


#4

모바일이라 간단하게 남깁니다

구간합과 함께 투포인터 쓰시면 O(n)에 가능할 것 같습니다


(Joel M) #5

reduceRight를 사용해서 간단하게 O(n) 안에 풀 수 있습니다. (모바일이라 일단 짧게 남깁니다~)

const solution = (arr, answer=[]) => {
   arr.reduceRight((acc, val) => { 
      const nextVal = acc+val
      answer.push(nextVal)
      return nextVal
   })
   return answer
}
const result = solution([1,2,3,4])
console.log(result) // [7,9,10]