SLiPP 스터디
Page tree
Skip to end of metadata
Go to start of metadata

풀이

Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 49.6 MB, less than 74.71% of Java online submissions for Product of Array Except Self.

Time Submitted

Status

Runtime

Memory

Language

02/18/2021 00:59Accepted1 ms49.8 MBjava
  • 소요시간:  총 45분 = 1차 접근(스터디 시간) 30분 +  2차 접근(추가 시간) 15분
Java- cleancode 했는데 별로 바뀌지 않았다
class Solution {
	public int[] productExceptSelf(int[] nums) {
		int n = nums.length;

		int[] output = new int[n];
		
		output[0] = 1;
		output[n-1] = 1;
		
		for (int i = 1; i < n; i++) {
			output[i] = output[i - 1] * nums[i-1];
		}
		
		int r = 1;
		for (int i = n - 1; i >= 0; i--) {
			outputs[i] *= r;
			r *= nums[i];
		}
		return output;
	}
}
Java - 1차답변 
class Solution {
	public int[] productExceptSelf(int[] nums) {
		int n = nums.length;

		int[] outputs = new int[n];
		
		outputs[0] = 1;
		outputs[n - 1] = 1;
		
		for (int i = 1; i < n; i++) {
			outputs[i] = outputs[i - 1] * nums[i-1];
		}
		
		int bottom = 1;
		for (int i = n - 1; i >= 0; i--) {
			outputs[i] *= bottom;
			bottom *= nums[i];
		}
		return outputs;
	}
}
Java - 주석 버전 
class Solution {
	public int[] productExceptSelf(int[] nums) {
		int n = nums.length;

		int[] outputs = new int[n];
		
		// TL;DR split array -> 해당하는 원소를 기준으로 배열을 나눔
		// 1. 해당 원소 값을 제한다 == 해당 원소를 기준으로 배열을 나눈다 
		// 2. ouput[i]  = (0 ~ i-1 원소의 곱) * (i+1 ~ len-1 의 곱)
		// 3. upper array : 0 ~ i-1 의 곱을 저장
		// 4. bottom array : i+1 ~ len-1 의 곱을 저장 

		// 맨 끝들 비어있는 값 채우기
		// 위 규칙이라면 i = 0 -> 0 ~ -1 원소의 곱이 되버리므로. n-1 도 마찬가지 
		outputs[0] = 1;
		outputs[n - 1] = 1;

		// upper array : 0 ~ i-1 의 곱을 저장
		// 왼쪽에서부터 for 로 곱해나감
		for (int i = 1; i < n; i++) {
			outputs[i] = outputs[i - 1] * nums[i-1];
		}
		
		// bottom array : i+1 ~ len-1 의 곱을 저장
		// 오른쪽 원소부터 곱해나감 
		int bottom = 1;
		for (int i = n - 1; i >= 0; i--) {
			outputs[i] *= bottom;
			bottom *= nums[i];
		}
		return outputs;
	}
}


Runtime: 216 ms, faster than 64.25% of Python online submissions for Product of Array Except Self.
Memory Usage: 20.9 MB, less than 57.00% of Python online submissions for Product of Array Except Self.

Python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        outputs = []
        outputs.append(1)        
         
        for i in range(1, n):
            outputs.append(outputs[i - 1] * nums[i-1])
         
        bottom = 1
        for i in range(n-1,-1,-1):
            outputs[i] *= bottom
            bottom *= nums[i]

        return outputs


접근방법 설명


접근 과정

1차 접근 - 로직은 맞지만 실제 코드 구현이 안됨

  • 스터디 시간 내에 접근한 방법
  • TL;DR split Array 해서 곱하기
  • 문제 분석
    • 문제 심플하게 만들기 위한 가정
      • array elements 수는 1개 이상
      • 32bit integer 범위 - array 를 어떤 요소 기준으로 쪼개고 곱해도 해당 범위를 벗어나지 않음. 
    • constraint
      • divison 사용하면 안됨 → division 말고 product 로 풀기
      • time complexity O(n) → sort 할 필요가 없으니까 단일 for statement 까지 이용가능
    • Follow up 
      • space complexity O(1)
  • pattern 찾기
    • 해당 원소 값만 빼고 나머지를 다 곱하기 → 각 계산마다 달라져야하는 기준점 = 해당 원소의 값 num[i]
    • num[i] 를 바꾸어주어야하는 값으로 두면 공통점이 보임 → 해당 원소 값 기준으로 앞의 모든 곱셈 값,  뒤의 모든 곱셈 값을 구한후 두 수를 곱하면 됨 
  • 그림으로 스케치
    • (문제 풀기 위한 초안이라 스케치가 알아보기 힘들 수 있어요)


2차 접근 - 로직 재점검, 코드 디버깅

  • 다시 기존 로직 손으로 상세하게 그리면서 점검함.
    • 맞는 거 같다. 왜 안되지? → 구현한 코드를 살펴보자. 
  • 문제 발견 - upper(해당 element 기준 왼쪽) 코드에서 계산한 값 output 에 값 안 넣음.
    • 문제 어떻게 발견했나? 
      • 로직 다시 손으로 그려보면서 잘못된 부분 깨달음.
  • 개선 : for statement 의 initial value 수정  → if statement 필요없어짐


3차 작업 - 스터디원에게 설명

  • 화이트보드코딩 테스트 대비 겸 설명을 위해 로직 정리해 그리기

4차 작업

  • 코드 깔끔하게 다듬기 - naming, 중복 코드 제거
  • python 으로 풀어보기
    • 주피터 환경 시도  - 바로 실행결과 보기 
      • 체크포인트 
        • auto complete delay 문제에 적응할 수 있을지
        • time 측정 어떻게 할 수 있을지
        • cell 실행 꼬이지 않을까? 전체 재실행으로 해야하나?

회고 - 개선 필요점

  • 경계값 테스트하기
    • for statement 의 initial value 를 다르게 잡아서 if 문이 추가로 필요했음.
  • 알고리즘에서 쓸 규칙적인 변수명 만들기

- 변수명이 왔다갔다해서 헷갈림. 좀 더 긴 솔루션에서는 내가 변수명에서 길 잃을듯. 변수명 만드는 것도 시간이 걸린다. 

  • 타임어택 방식 익숙해지기
    • 1차 접근에서 로직은 맞는 거 같은데 당황해서 디버깅이 안됨. 타임어택이라 긴장함
  • 개발 환경 미리 세팅하기 - 프로젝트 생성, 템플릿, 지우개 사기
    • IDE - IDE 세팅하느라 오래 걸림. python 과 Java 둘 중 어떤게 쓰는게 편할지 몰라서 양쪽에 잡다보니 설정이 꼬임 → colab 으로
    • 연필로 적는데 지우개가 없어서 메모가 더러워짐. → 샀다. 
  • 고민 → 결정 : 1차 접근 python 으로, 2차 다시 풀기는 Java도 함께 풀자.
    • 어떤 언어로 풀지 미리 마음을 정해놓아야하나? python 이 문자열 처리에서는 편리함. 많은 데이터 케이스 처리할 때엔 Java 가 속도 이득
    • python 이 battery-included 정책도 있어서 자료형 처리도 편하고, 변칙 유형에  유연하게 대응할 수 있다고 함. 
    • Java 가 약간의 속도 이득이 있을 수 있으니 둘 다 보기. 




  • No labels