프라이D
프라이Develog(❁´◡`❁)
프라이D
전체 방문자
오늘
어제
  • ALL (378)
    • TDD, Cleancode with JavaScr.. (5)
    • 프로젝트 (32)
      • work (3)
      • 직접 만드는 기술 블로그 (2)
      • 데일리 옥션 (19)
      • 모락모락 (8)
    • Computer Science (1)
    • Algorithm & 자료구조 (94)
      • 알고리즘 w.JavaScript (53)
      • 자료구조 (5)
      • (인프런) 자바스크립트 알고리즘 문제풀이 (34)
    • JavaScript (45)
      • JavaScript (41)
      • 모던 자바스크립트 Deep Dive (4)
    • WEB (13)
    • 회고 (12)
    • TIL (109)
    • WIL (7)
    • Stacks (20)
      • React.js (6)
      • Next.js (1)
      • Redux (3)
      • Node.js (2)
      • GIT (2)
      • SAP (1)
    • 15일 메이킹 프로젝트 (15)
    • 이전 기록 (14)
    • ETC. (5)
    • ---------------2021 (6)
      • 내일배움단-웹개발 5주 (2)
      • 정보처리기사 (4)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • nomadcoder
  • nomadcoders
  • 투포인터알고리즘
  • Til
  • 자바스크립트비트마스크
  • vanilaJS
  • 스파르타코딩클럽
  • 알고리즘
  • 코딩프로젝트
  • MySQL
  • JavaScript
  • 국비지원
  • 내일배움카드
  • 자바스크립트알고리즘
  • 자바스크립트
  • 2023 인프콘 후기
  • 내일배움단
  • 모던자바스크립트딥다이브
  • 코드스테이츠
  • 비트마스크

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
프라이D

프라이Develog(❁´◡`❁)

Algorithm & 자료구조/(인프런) 자바스크립트 알고리즘 문제풀이

[알고리즘] 부분 수열의 합 2

2022. 2. 17. 22:13

문제

N개의 수로 이루어진 수열이 주어집니다. 이 수열에서 연속부분수열의 합이 특정숫자 M이하가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=5, M=5이고 수열이 다음과 같다면
1 3 1 2 3
합이 5이하가 되는 연속부분수열은 {1}, {3}, {1}, {2}, {3}, {1, 3}, {3, 1}, {1, 2}, {2, 3}, {1, 3, 1}로 총 10가지입니다.

풀이

function solution(m, arr){
    let answer=0;
    let sum =0;
    let lt=0;
    for(let rt=0;rt<arr.length;rt++){
        sum+=arr[rt]; //sum에 현재 rt 값을 누적
        while(sum>m) {
            sum-=arr[lt++];
        } //sum>m이 참일 때만 실행. sum에서 현재 lt 값을 빼주고 lt를 증감시킨다. sum>m이 거짓이 될 때까지.
        answer+=(rt-lt+1); //이외의 경우는 answer에 현재 rt 값을 포함해 만들어지는 모든 참의 경우의 수를 누적. 
    }
    return answer;
}

let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));
  • 나의 오답보다 훨씬 직관적이고 깔끔하다. while문을 잘 사용해야 할 것 같다.

나의 오답...

 function solution(m, arr){
    let answer=0;
    let sum =0;
    let lt=0;
    for(let rt=0;rt<arr.length;rt++){
        sum+=arr[rt]; //sum에 현재 rt 값을 누적
        if(sum<=m) answer+=(rt-lt+1); 
        //if문으로 조건에 맞는지 검증 후, 맞다면 현재 값을 포함한 모든 참의 경우를 answer에 누적.
        if(sum>m) {
            sum-=arr[lt++];
            if(sum<=m)answer+=(rt-lt+1);
        }; //다음 if문에서 조건에 부합하지 않는 경우 sum에서 lt값을 뺀 후 증감. 
        //다시한번 sum이 조건에 부합하는지 확인 후 참이되면 answer에 모든 경우 누적.
    }
    return answer;
}

let a=[1, 3, 1, 2, 3];
console.log(solution(5, a));
  • 조건에 부합하지 않는 경우의 누적과정에서 누락된 부분이 있는듯...
  • 부끄럽지만 나중에 보라고 올린다.
저작자표시 (새창열림)

'Algorithm & 자료구조 > (인프런) 자바스크립트 알고리즘 문제풀이' 카테고리의 다른 글

[알고리즘] 아나그램 (해쉬)  (0) 2022.02.22
[알고리즘] 학급회장 (해쉬)  (0) 2022.02.22
[알고리즘]연속 부분 수열 1 - 투포인터 알고리즘  (0) 2022.02.13
[알고리즘] 공통원소 구하기 - 투포인터 알고리즘  (0) 2022.02.08
[알고리즘]k번째 큰 수  (0) 2022.02.06
    'Algorithm & 자료구조/(인프런) 자바스크립트 알고리즘 문제풀이' 카테고리의 다른 글
    • [알고리즘] 아나그램 (해쉬)
    • [알고리즘] 학급회장 (해쉬)
    • [알고리즘]연속 부분 수열 1 - 투포인터 알고리즘
    • [알고리즘] 공통원소 구하기 - 투포인터 알고리즘
    프라이D
    프라이D
    틀린내용 정정 및 개선사항은 언제든지 댓글 달아주세요 :D

    티스토리툴바