js 알고리즘(연속된수열1)

문제

배열에 무작위 값들(list)과 특정 수(n)가 주어졌을 때 배열 안에서 연속된 수를 더하면 n이 되는 경우의 수를 구하는 문제

ex) let list = [1,3,2,1,1,5,1,1]
let n = 8
let result = 3

나의 풀이

• 연속된 수를 더해서 n이 나오는 값을 찾아야 하기 때문에 우선 배열의 첫부분을 기준점으로 하여 뒤의 수를 차례로 더한 다음 해당 값이 나오면 result 값을 늘려주고 값을 넘으면 기준점을 다음부분으로 넘겨서 반복하도록 해결했다.

let list = [1,3,2,1,1,5,1,1]
let n = 8
let result = 0;
for(let i = 0; i < list.length; i++){
  let sum = list[i]; // 총합의 첫 기준점을 list[i]로 잡음
  for(let j = i+1; j < list.length; j++){ // i 다음 수부터 차례로 더해주기 위해 이중 for문
    sum = sum + list[j]
    if(sum > n) {
      break; // sum 이 n을 넘으면 break 하여 다음 수로 넘기기
    }else if(sum === n){
      result++;
      break;
    }
  }
}
//result = 3

• 문제점
  문제는 해결할 수 있지만 for 문을 두번을 사용해서 시간 복잡도가 O(n2)으로 효율적이지 못함

효율적인 풀이

• 0을 기준으로 하는 변수 t를 설정해줌 for문은 한번만 돌리면서 처음 수부터 계속해서 더해주고 n을 넘으면 다시 돌아오는게 아닌 더한 맨 앞의 배열 수만 빼준다. 그리고 다시 뒤에 차례대로 더하면서 n이 나오면 result 값을 늘려줌
  ex) [1,2,3,1,1]
  n=5

1. 1+2+3 = 6 --> 맨 앞의 수인 1을 빼준다.
2. 2+3 = 5 --> n이 5이기 때문에 result + 1을 해줌
3. 3+1 = 4 --> 맨앞의 수인 2을 빼고 뒤의 요소인 1을 더해줌

let list = [1,3,2,1,1,5,1,1]
let n = 8
let t = 0;
let result = 0;
let sum = 0;
for(let i = 0; i < list.length; i++){
  sum = sum + list[i]
  if(sum === n) result++;
  if(sum >= n){
    sum = sum - list[t++]
    if(sum === n) result++;
  }
  
}
//result = 3

결론

두번째 풀이는 for를 한번만 사용하기 때문에 시간 복잡도가 훨씬 줄어드는 것을 알 수 있다.
for 문을 좀 더 줄이는 방향으로...