codewar: Sum of Parts

문제

 - https://www.codewars.com/kata/5ce399e0047a45001c853c2b

 

문제풀이

 - 주어진 배열을 순회하면서, 합을 구하는 구하는 문제입니다.

  - 0 번째는 0 ~ array.length 까지의 합.

  - 1 번째는 1 ~ array.length 까지의 합.

  - 쭉쭉쭉 array.length-1 번째는 array.length-1 ~ array.length까지의 합.

 

 - 이렇게 구하는데, 순차적으로 구하게 될 시에는 이중 for문을 사용하게 되므로, O(N^2)의 시간 복잡도가 됩니다. 그렇기에 이렇게 풀어서 제출을 하게 되면, Timeout 으로 fail이 나게 됩니다.

 - 뒤집어서 계산을 하여 넣게 된다면 for문 한번만 수행하게 되면 되므로, O(N)의 시간복잡도로 계산이 됩니다.

class SumParts {

  public static int[] sumParts(int[] ls) {
    // your code
    int[] result = new int[ls.length+1];
		
	result[ls.length] = 0;
		
	for(int i=ls.length-1; i>=0; --i) {
		result[i] += ls[i] + result[i+1];
	}
	return result;
  }
}