2018-06-04-2.md

이 문제의 저작권은 매일프로그래밍(https://mailprogramming.com/)에 있습니다.

문제

• 매일프로그래밍 - 실리콘밸리 패키지 문제 12
• 각 원소가 자신을 뺀 나머지 원소들의 곱셈이 되게하라.

풀이

• 각 원소를 제외한 곱의 형태가 어떤지를 파악하면 분해해서 구할 수 있다.
• 문제의 예제의 경우 아래처럼 표현이 가능

results = [
a[1]*a[2]*a[3]*a[4],
a[0]*a[2]*a[3]*a[4],
a[0]*a[1]*a[3]*a[4],
a[0]*a[1]*a[2]*a[4],
a[0]*a[1]*a[2]*a[3]
]

left = [
1,
a[0],
a[0]*a[1],
a[0]*a[1]*a[2],
a[0]*a[1]*a[2]*a[3]
]

right = [
a[1]*a[2]*a[3]*a[4],
a[2]*a[3]*a[4],
a[3]*a[4],
a[4],
1
]

코드

inputs = [1, 2, 3, 4, 5]
outputs = [] # [120, 60, 40, 30, 24]

# O(n^2)
outputs = []
for i in inputs:
	tmp_value = 1
	for j in inputs:
		if( i==j ): continue
		tmp_value *= j
	outputs.append(tmp_value)

print(outputs)


# O(n), 나눗셈을 사용
multiples = 1
outputs = []
for i in inputs:
	multiples *= i

for i in inputs:
	outputs.append(int(multiples/i))

print(outputs)


# O(n), 2차원배열을 이용 => 정답
outputs = []

left = [1]
tmp_value = 1
for i in range(0, len(inputs)-1):
	tmp_value = tmp_value * inputs[i]
	left.append(tmp_value)


right = [1]
tmp_value = 1
for i in range(0, len(inputs)-1):
	tmp_value = tmp_value * inputs[(len(inputs)-1)-i]
	right.insert(0,tmp_value)

for i in range(0, len(inputs)):
	outputs.append(left[i] * right[i])

print(outputs)

반성

• 그려보면 알 수 있는데 그 부분을 캐치하지 못했다.

참고자료

• http://bestcoding.tistory.com/36