[매일프로그래밍] 원소가 자신을 뺀 나머지 원소들의 곱셈

안녕하세요, 매일프로그래밍 이번주 문제입니다.

 

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

단, 나누기 사용 금지, O(n) 시간복잡도

 

Given an integer array, make each element a product of all element values without itself.

 

예제)

input: [1, 2, 3, 4, 5]

output: [120, 60, 40, 30, 24]

접기

	@Test
	public void algorithmTest(){

		try {

			/*			
			Given an integer array, 
			make each element a product of all element values without itself.

			input: [1, 2, 3, 4, 5]
			output: [120, 60, 40, 30, 24]
			*/

			int[] arrElmt = new	int[] {1, 2, 3, 4, 5};
			int[] arrResult = new int[arrElmt.length];

			arrResult = remainMultiply(arrElmt);

		} catch (Exception e) {

			 e.printStackTrace();
		}

	}

    
    
    private int[] remainMultiply(int[] arrElmt) {

		int max = arrElmt.length;
		int[] One = new int[max];
		int[] Two = new int[max];
		int[] arrResult = new int[max];

		int init = 1;

		for (int i = 0; i < max; i++) {

			One[i] = init;
			init *= arrElmt[i];
			System.out.println(init);
		}

		init = 1;
		for (int i = max -1; i >= 0; i--) {

			Two[i] = init;
		    init *= arrElmt[i];
		    System.out.println(init);
		}

		for (int i = 0; i < arrResult.length; i++) {
			arrResult[i] = One[i] *Two[i];
			System.out.println("arrResult +++ " +arrResult[i]);
		}

		return arrResult;
	}

 

 

 

따라서 시간복잡도가 O(n)이 되려면 반복문안에 또 다른 반복문을 사용해서는 안됩니다.

단, 여러개의 반복문을 독립적으로 사용하게 되면 O(b*n) = O(n) 이므로 독립적으로는 여러개를 사용해도 상관이 없습니다.