프로그래머스 연속 부분 수열 합의 개수 C++

 

자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇가지인지 반환하는 문제이다.

 

 

원형으로 된 수열  벡터 elements 가  주어지고

길이 1부터 시작해 elements의 길이만큼의 연속되는 수열의 합을 구한다.

 

길이가 1 이라고 가정하였을떄는 각 원소의 값을 저장하면 될것이고

길이가 2라면,   벡터의 0번째 + 1번째,   1 + 2,   2 + 3,  3 + 4,  4 + 5 ...... end + 0 이런식으로 되겠다(원형이기 때문)

즉 길이가 3일 경우에는    0 + 1,  1 + 2,  2 + 3, .....   (end - 1) + end + 0,   end + 0 + 1 이렇게 되겠다.

 

경우의 수를 구하는 문제로 중복된값은 필요가없고, 순서대로 구할 필요도 없기에

unordered_set을 이용해 풀었다. - 중복값은 알아서 저장을 안하기 때문

 

 

 

 

 

원형 수열 이기 때문에

원형 수열의 특성을 선형 배열로 변환하여 수열을 2배 확장된것처럼 만들어, 연속 부분 수열을 계산할 경우의 복잡함을 덜고, 배열 인덱스가 넘어가지 않도록 처리한다.

 

원래의배열이 7 9 1 1 4 라면 7 9 1 1 4 7 9 1 1 4 이런식으로 한다.

 

배열의 범위를 넘어섰을 경우 (start + i) % n = (3 + 2) % 5 = 0이 되어, elements[0]을 다시 참조할 수 있게 된다.

 

예시를 들면 start가 0인 경우 i가 증가하면서 인덱스를 탐색할때, start + i가 배열의 크기인 n을 넘어가게 되면 배열을 순환 시킨다.

 

n이 5인 경우 

 

start = 0

i = 0 : (0 + 0) % 5 = 0 % 5 = 0, 즉 인덱스 0 에 해당하는 7을 가져오게 되고,

i = 1 : (0 + 1) % 5 = 1 % 5 = 1, 즉 인덱스 1 에 해당하는 9를 가져온다

 

start가 3이라면

i = 1 : (3 + 1) % 5 = 4 % 5 = 4, 인덱스 4에 해당하는 값 4를 가져옴

i = 2 : (3 + 2) % 5 = 5 % 5 = 0; 인덱스 0에 해당하는 값 7을 가져온다 이 부분부터 원형 수열의 순환이 시작된다.

i = 3 : (3 + 3) % 5 = 6 % 5 = 1, 인덱스 1에 해당되는 값 9 순환이 잘이루어지고 있는것을 알 수 있음

 

start에서 i번 째로 이동한 위치를 나타내고

% n은 그 값이 n을 넘어간 경우 인덱스를 다시 0부터 시작하게 만들어 순환시켜주어  (end - 1) + end + 0 이런 계산을 할 수 있게 해준다.