연속 부분 수열 합의 개수 (원형 수열)

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

처음에 문제를 한참 읽었다

도대체 뭐지

원형 수열이라는 부분에서 한바퀴를 더 돌아서 더해질 수 있다는걸 알아서

길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.

이 부분이 헷깔렸는데 그냥 [ 7, 9, 1, 1, 4 ]이 주어졌을 때

소팅하지말고

길이가 1일 때는 중복되지 않은 숫자들은 7 9 1 4 이고 (정렬하면 1 4 7 9)

길이가 2일 때 7+9, 9+1, 1+1, 1+4, 4+7(원형 수열의 특징으로 앞이랑 뒤 숫자가 이어져있다고 생각하면 됨)

합은 16 10 2 5 11 이므로 정렬하면 2 5 10 11 16

길이가 3일 때는 7+9+1, 9+1+1, 1+1+4, 1+4+7, 4+7+9

합하면 17 11 6 20 12

정렬하면 6 11 12 17 20

 

길이가 4일 때 7+9+1+1, 9+1+1+4, 1+1+4+7, 4+7+9+1

합하면 18 15 13 21

정렬하면 13 15 18 21

 

길이가 5일 때는 그냥 모든 합 22가 나온다

 

이문제는 중복을 허용하지 않는 Set으로 접근하면 쉬울 것 같고

길이1과 마지막 길이 일때는 그냥 수동 계산이 좀 더 효율적일 것이다 

길이 1로 Set을 초기화 해주고

마지막 길이는 그냥 그 수들의 합을 더해서 넣기

이렇게 초기화해서 풀어내면 될 것

그리고 반복문을 2부터 마지막길이 전까지로 돌리면 됨

원형수열이라 이게 좀 복잡할 것 같다

첫 번째부터 마지막 수까지 더하는거야 그냥 하면 되지만

원형수열이므로 3개부터는 마지막번째와 첫번째, 두번째 이런식의 조합이 가능해 진다 

그래서 그냥 순열을 이용해서 푸는게 편할 수도?

https://yongfront.tistory.com/86

Summer/Winter Coding(~2018) > 소수 만들기

 

이 글을 참고

 

대충 이렇게 하면 되지 않을까? 했는데 값이 이상하게 찍힘

이럴 땐 개발자도구 코드 스니펫으로 디버깅해보기

 

많은 오류들을 찾음

 

1. 일단 result.length 에서 result 는 배열이 아닌 객체이므로 size로 전달해줘야하고

2. result.add(...순열구하기()) 식으로 더할수는 없음

Set.add(...values)가 작동하지 않는 이유는 Set.prototype.add 메서드가 단일 값을 추가하도록 설계되었기 때문

...values는 배열을 개별 요소로 분해하지만, Set.add 메서드는 단일 값만을 받기 때문에 오류가 발생

쉽게 말하면 자바스크립트의 Set 객체는 고유한 값들의 집합을 저장하는 데이터 구조이고

Set 객체의 add 메서드는 한 번에 하나의 값만 추가할 수 있도록 설계되어 있다는 것

 

 

3. 그리고 치명적인 오류 

원형 수열은 순열로 안된다 

저걸 맞는 소스로 고쳐서 풀어봤더니 

[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

이 올바른 값인데 여기서 8, 14가 빠져있는 이유는 원형 수열의 특징으로 연속된 숫자만 더할 수 있다는 제약이 있음

Set(20) { 7, 9, 1, 4, 22, 16, 8, 11, 10, 13, 2, 5, 17, 20, 12, 14, 6, 18, 21, 15 }

이렇게 8, 14도 더해버려서 망함

이렇게는 안되고 합 구하는 순열을 좀 바꿔서 원형 수열의 합을 구할 수 있도록 풀어야 함

 

 

원형 수열의 합을 구하려면 

원본 배열을 두번 복사해서 붙이면 됨 (자력으로는 생각못해냄)

 

그 후 합을 구해 준 후 

 

 

size를 리턴한다