프로그래머스/Level2(JS)

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

2023. 11. 28. 10:21
목차
  1. 연속 부분 수열 합의 개수
  2. ❓ 문제설명
  3. 🚫 제한조건
  4. ✔ 입출력 예
  5. 💡 풀이
  6. 📝 해설
  7. 📚 참고자료
728x90
반응형

연속 부분 수열 합의 개수

❓ 문제설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

🚫 제한조건

3 ≤ elements의 길이 ≤ 1,000

1 ≤ elements의 원소 ≤ 1,000

✔ 입출력 예

elements result
[7,9,1,1,4] 18

💡 풀이

function solution(elements) {
  const double = [...elements, ...elements]

  const set = new Set()
  for(let i=0; i < elements.length; i++) {
    let sum = 0
    for(let j=0; j < elements.length - 1; j++) {
      sum += double[i+j]
      set.add(sum)
    }
  }

  return set.size + 1
}

📝 해설

 원형 수열의 특징은 마지막 원소 다음이 다시 처음 원소로 이어진다는 것이다. 이 점을 활용해서 해당 부분수열을 2번 이어 붙인 배열을 만들고 첫번째 원소부터 부분수열의 합을 확인하여 set으로 모았다. 이 때 전체를 더하는 건 빼는데 이는 전체를 더한건 모두 똑같은데 모든 원소를 돌면서 무의미하게 반복적으로 더하지 않고 마지막에 set.size + 1 로 하는 것이 더 간단하기 때문이다.

📚 참고자료

- https://kimby.tistory.com/57 (Set 객체)

728x90
반응형
저작자표시 (새창열림)
  1. 연속 부분 수열 합의 개수
  2. ❓ 문제설명
  3. 🚫 제한조건
  4. ✔ 입출력 예
  5. 💡 풀이
  6. 📝 해설
  7. 📚 참고자료
'프로그래머스/Level2(JS)' 카테고리의 다른 글
  • [프로그래머스] n^2 배열 자르기 - JS
  • [프로그래머스] 괄호 회전하기 - JS
  • [프로그래머스] 귤 고르기 - JS
  • [프로그래머스] 멀리 뛰기 - JS
KimBY
KimBY
웹개발과 관련된 개발지식 모음
KimBY
B.Y Kim의 개발노트
KimBY
전체
오늘
어제
  • 분류 전체보기 (99)
    • 사소한 개발지식 (49)
      • PHP (2)
      • JavaScript (15)
      • NodeJS (0)
      • JAVA (2)
      • 잡?지식 (4)
      • 로드맵(FE) (22)
      • React (4)
    • 개발노트 (6)
      • 포트폴리오사이트 (6)
    • 프로그래머스 (33)
      • Level1(JS) (0)
      • Level2(JS) (33)
    • 백준알고리즘 (11)
      • 단계별로 풀어보기3(for문) (11)
    • 잡담 (0)

인기 글

최근 글

최근 댓글

태그

  • 단계별로풀어보기
  • Level2
  • frontend
  • javascript
  • react
  • CSS
  • 프로그래머스
  • FE로드맵
  • 백준알고리즘
  • 로드맵
hELLO · Designed By 정상우.
KimBY
[프로그래머스] 연속 부분 수열 합의 개수 - JS
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.