[프로그래머스] 연속 부분 수열 합의 개수

쿼카쿼카·2023년 2월 25일
0

알고리즘

목록 보기
40/67

코드

// function solution(elements) {
//     let ans = new Set();
    
//     for(let i=0; i<elements.length; i++) {
//         for(let j=0; j<elements.length; j++) {
//             let sum = 0
//             for(let k=j; k<=i+j; k++) {
//                 if(k >= elements.length) {
//                     sum+=elements[k-elements.length];
//                     continue;
//                 }
//                 sum += elements[k];
//             }
//             ans.add(sum);
//         }
//     }    
//     return ans.size;
// }

// 펼칠 생각을 해보자
function solution(elements) {
  const doubleElem = elements.concat(elements);
  const ans = new Set();
  
  for(let i=0; i<elements.length; i++) {
      let sum = 0;
      for(let j=0; j<elements.length; j++) {
          sum += doubleElem[i+j];
          ans.add(sum);
      }
  }
  
  return ans.size
}

3중 포문

  • 첫 for는 더할 길이
  • 두 번째는 시작할 자리
  • 세 번재 포문은 더할 요소들
  • 성공은 했으나 3중 포문부터 이미 겁나 찝찝하죠?

펼칠 생각을 해보자

  • 이거를 펼쳐서 한 줄 더 합치면...
  • 이중 포문으로 해결 가능
  • 3중 포문일 때는 한 자리씩 더할 때! 두 자리씩 더할 때! 였는데 여기서는 시작자리를 기준으로 시작자리 하나 둘 셋 넷 다 더해! 이렇게 진행
profile
쿼카에요

0개의 댓글