코딩테스트 #11

정수로된 배열이 주어지면, 각 원소가 자신을 뺀 나머지 원소들의 곱셈이 되게하라.

단, 나누기 사용 금지, 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를 얻을 수 있다.

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;
}