문제
어느 날 철호는 어떤 "자연수로 이루어진" "원형 수열"의 "연속하는 부분 수열의 합"
으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다.
원형 수열이란 "일반적인 수열에서 처음과 끝이 연결된 형태의 수열"을 말합니다.
예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
4 7
1 9
1
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도
일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때,
"원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수"를
return 하도록 solution 함수를 완성해주세요.
예시
[입출력 예]
elements result
[7,9,1,1,4] 18
[입출력 예 설명]
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]
프로세스
그러니까 배열의 index 로부터 index 가 총 5개라면
길이가 1 : index[0], index[1], index[2], index[3], index[4]
길이가 2 : index[0,1], index[1,2], index[2,3], index[3,4], index[4,0]
...
길이가 4 : index[0,1,2,3] index[1,2,3,4] index [2,3,4,0] index[3,4,0,1]
...
이렇게 더한다는것.
1) slice 를 사용해서 배열을 토막내고
2) 토막낸 배열을 각각 더해서, 새 배열에 집어넣고
3) 중복되는 숫자를 제거해서
4) 총 갯수가 몇개나 되는가? 를 찾으면된다.
사용
1. reduce()
2. slice()
3. 스프레드 연산자를 통한, 배열 직접 변경
4. new Set() 의 중복 검사
내코드
function solution(elements) {
const answerArray = [];
for (let j = 0; j < elements.length; j++) {
for (let i = 0; i < elements.length; i++) {
let remakingArray = elements.slice(i, i + j + 1);
if (remakingArray.length < j + 1) { // 스프레드 연산자를 이용해서 배열을 직접 변경하고
remakingArray = [
...remakingArray,
...elements.slice(0, j - remakingArray.length + 1),
];
}
answerArray.push(remakingArray.reduce((a, b) => a + b)); // 최종 계산된 값만 push 했다.
}
}
const answer = [...new Set(answerArray)].length;
return answer;
}
'CS와 언어, 라이브러리 이론 > 알고리즘-이론과 실전' 카테고리의 다른 글
8. [실전] - 문자열 나누기 (1) | 2023.01.18 |
---|---|
7. [실전] - 우박수열 (1) | 2023.01.18 |
5. [실전] - 귤 고르기 (1) | 2023.01.18 |
3. [실전] - 가장 가까운 글자찾기 (0) | 2023.01.18 |
2. [실전] - 연속되는 자연수 배열중 빈 숫자 찾기 (0) | 2023.01.18 |
댓글