문제
문제 조건
- nums[]라는 배열이 주어진다.
- answer[]를 return 해야한다.
2-1. answer[i]는 nums[i]'(자신을)'를 제외한 모든 요소와 곱셈을 해야한다.
2-2. example1 기준)
nums[0] = 1 = 2 x 3 x 4 = 24
nums[1] = 2 = 1 x 3 x 4 = 12
nums[2] = 3 = 1 x 2 x 4 = 8
nums[3] = 4 = 1 x 2 x 3 = 6
3.nums는 32비트 정수를 보장한다.
4.나눗셈을 사용하지 않고 O(n)을 만족해야한다.
어떻게 해결할 것인가?
항상 이런 문제들은 어디서부터 실마리를 잡는 지가 중요하다.(사실 이게 99% 지분인 거 같다)
일단 answer[]부터 만들고 보자
-
answer[] = nums[] 이니까
nums.length만큼 answer[]를 만들어주자
-
내가 가장 어려워하는 부분이다. 여기서부터 진도가 막힌다.
갑자기 생각났다
return도 만들어주자
-
여기를 보면서 머릿속으로 계속 생각한다.
-
한번에 계산하려고 하니 잘 안된다.
그렇다면 나눠서 계산할 방법은 있는 지 고민해본다.
(40분째다) -
nums에서 생각이 계속 머무는데 답이 안보인다.
다른 곳에서 시작할 수 있는 곳이 있는지 찾아본다.
answer를 기준으로 계산할 곳을 nums[], answer[] 값을 비교해보자 -
nums = [1,2,3,4]
result = [0,0,0,0]
이렇게 보니까 훨씬 낫다
뭔가 실마리가 있을까? -
결국 여기서 막혀버렸다.
답안을 분석하고 설명하겠따.
nums = [1,2,3,4]
result = [1,0,0,0]이게 바로 문제의 실마리였다.
result[0] = 1;
추가하도록 하겠다.
- 자기 자신을 제외한 숫자를 곱해야하니 nums[0]과 answer[0]을 곱해서 answer[1]에 1차 결과를 넣어준다.
answer[1]에 넣어야하니 초기값 int i = 1;
0으로 시작하지 않으니 nums.length 역시 -1을 넣지 않았다.
왼쪽에서 오른쪽 순서대로 자기 자신을 제외하고 곱해준다.
nums = [1,2,3,4]
answer[1] = [1,1,0,0]
answer[2] = [1,1,2,0]
answer[3] = [1,1,2,6]
answer = [1,1,2,6]
이 나올 것이다.
9.여기서도 이해가 되진 않지만 int right = 1; 을 추가해준다.
- 여기서부턴 생각을 포기했다.
일단 코드부터 분석하자
for문을 역산으로 돌려준다
nums = [1,2,3,4]
answer = [1,1,2,6]
right = 1
answer[3] -> answer[2] -> answer[1] -> answer[0]
answer[3] = 6(answer[3]) x 1(right) = 6
right = 1(right) x 4(nums[3])
answer[2] = 2(answer[2]) x 4(right) = 8
right = 4(right) x 3(nums[2]) = 12
answer[1] = 1(answer[1] x 12(right) = 12
right = 12(right) x 2(nums[1]) = 24
answer[0] = 1(answer[1] x 24(right) = 24
answer = [24,12,8,6]
- 이러한 구조로 연산을 하게 된다.
사실 뒷부분부터는 이해하기가 너무 힘들었다.
더 쉽게 생각하는 방법이 있었을까 싶다.
느낀 점
그냥 수에 대한 감각 자체가 매우 부족한 거라는 사실을 깨달았다.
스스로 많이 풀어보되 더 좋은 답들을 찾아보고 분석해보면서
그 안에 어떤 패턴들이 더 숨어있는지 확인해봐야겠다
이런 순간순간들의 감각들이 실력에 엄청난 영향을 미칠 것이라는 생각이 든다.
