Today I Learned

오늘 할일
1. LeetCode
2. 강의
3. 싱가포르 일정 완성 https://velog.io/@gogogi313/Today-I-Learned-vznmvcwf
4. 봉사실적 확인 20시간 30분 / 30시간노인복지관 신청완료

오늘 한일
1. LeetCode

• 238. Product of Array Except Self는 배열에서 자기자신을 제외한 나머지 숫자들의 곱을 자신에 인덱스에 저장하는 배열을 리턴하는 문제이다. 초기에 작성한 코드에서 Time Limit Exceeded가 발생하여 불필요한 리스트 변환을 제거하고 다시 작성하였는데도 같은 문제가 발생하였다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result=new int[nums.length];
        for(int index=0; index< nums.length; index++){
            int multiple_result=1;
            for(int index_input=0; index_input<nums.length; index_input++){
                if(index==index_input)//자기자신 제외
                    continue;
                if(nums[index_input]==0){//하나라도 0있으면 결과는 0이기에 탈출
                    multiple_result=0;
                    break;
                }
                multiple_result*=nums[index_input];
            }
            result[index]=multiple_result;
        }
        return result;
    }
}

최적화를 추가로 진행해야 한다.
- 1의 값은 굳이 곱하지 않고 바로 패스
- 0이 아닌 값을 stream().reduce()로 전체 곱 계산한 후 자기자신을 도로 나눔

문제를 자세히 읽어보니 복잡도 제한이 있었다.
You must write an algorithm that runs in O(n) time and without using the division operation.
기존의 코드는 이중 for문이 사용되기에 복잡도 O(n^2)으로 수행된다.
이를 해결하기 위해 최적화가 되어있는 stream api를 적극 사용하도록 코드를 수정하였다.
접근방법은 다음과 같다. 모든 배열의 곱을 계산전에 구해둔 다음, 각각의 인덱스 값을 빼서 자신을 제외한 모든 값의 곱을 더하는 것이다. 이때, 자신이 0인 경우 기존의 값이 어떤 값인지 역으로 구해낼 수 없기 때문에, 추가적으로 api함수를 이용해 예외처리를 해주었다. 예외처리 역시 stream api를 사용하여 구현하여 최대한의 최적화를 기대했다.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result=new int[nums.length];
        int total_multiple=Arrays.stream(nums).reduce((a,b)->a*b).getAsInt();
        for(int i=0; i<nums.length; i++) {
            if(nums[i]!=0)
                result[i] = total_multiple / nums[i];
            else
                result[i] = Arrays.stream(nums,0,i).reduce((a,b)->a*b).orElse(1)
                        *Arrays.stream(nums,i+1,nums.length).reduce((a,b)->a*b).orElse(1);
        }
        return result;
    }
}

확실히 stream api의 최적화가 정말 잘 되어있는 듯 하다. reduce의 내부 코드를 살펴보니 다음과 같이 명시되어 있다.

내부적으로 병렬처리를 통해 훨씬 빠른 속도로 연산이 가능하게 처리된 것으로 보인다.