정수로된 배열이 주어지면, 각 원소가 자신을 뺀 나머지 원소들의 곱셈이 되게하라.
단, 나누기 사용 금지, O(n) 시간복잡도
예제)
input: [1, 2, 3, 4, 5]
output: [120, 60, 40, 30, 24]
문제를 보자마자 쉽다 라고 생각했는데 시간복잡도가 O(n)에다가, 나누기를 사용할 수 없다..
공간을 활용해서 풀어야한다.
input과 output의 관계를 살펴보자.
input array = [ array[0]. array[1], array[2], array[3], array[4] ];
output answer = [ array[1] * array[2] * array[3] * array[4] ,
array[0] * array[2] * array[3] * array[4],
array[0] * array[1] * array[3] * array[4],
array[0] * array[1] * array[2] * array[4],
array[0] * array[1] * array[2] * array[3] ]
으로 나오는 것을 알 수 있다.
output answer = [ array[1] * array[2] * array[3] * array[4] ,
array[0] * array[2] * array[3] * array[4],
array[0] * array[1] * array[3] * array[4],
array[0] * array[1] * array[2] * array[4],
array[0] * array[1] * array[2] * array[3] ]
pre = [ 1,
array[0],
array[0] * array[1],
array[0] * array[1] * array[2],
array[0] * array[1] * array[2] * array[3] ]
after = [ array[1] * array[2] * array[3] * array[4],
array[2] * array[3] * array[4] ,
array[3] * array[4] ,
array[4],
1]
해법은 이것이다. 배열을 2개 만든다. (빨간색, 초록색으로 표시된 부분)
그 후에 두 배열의 원소들을 서로 곱해주면 answer를 얻을 수 있다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | public static void main(String[] args){ int[] param = {1, 2, 3, 4, 5}; solution(param); } public static int[] solution(int[] param){ // 배열생성 int[] pre = new int[param.length]; int[] after = new int[param.length]; int product = 1; for(int i=0; i<param.length; i++){ pre[i] = product; product *= param[i]; } product = 1; for(int i=param.length-1; i>=0; i--){ after[i] = product; product *= param[i]; } // 정답구하기 int[] answer = new int[param.length]; for(int i=0; i<param.length; i++){ answer[i] = pre[i] * after[i]; } return answer; } | cs |
