풀이
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:59 | Accepted | 1 ms | 49.8 MB | java |
- 소요시간: 총 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; } }
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 실행 꼬이지 않을까? 전체 재실행으로 해야하나?
- 체크포인트
- 주피터 환경 시도 - 바로 실행결과 보기
- leetcode 해설 보기
- 사람들이 다 푼 그 로직이다.
- 변수명 : L , R, answer 임 와우. 좋네.
- for i in reversed(range(length)) 를 썼다. 우왕. 보기 쉽고 좋네.
- discussion 에서 vote 수 높은 solution 보기
- 거의 비슷한 로직으로 푸네.
- for 하나로 풀기 - negative indexing! pythonic! 마음에 든다.
- Python
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # 초기 값을 아예 이렇게 둬서 하나하나씩 처리할 필요가 없고, 빠름 ans = [1] * len(nums) left = 1 right = 1 for i in range(len(nums)): ans[i] *= left # negative indexing 완전 좋아 ans[-1-i] *= right left *= nums[i] right *= nums[-1-i] return ans
- 코드가 더 짧다.
- https://leetcode.com/problems/product-of-array-except-self/discuss/65638/My-simple-Java-solution
- 변수명
- https://leetcode.com/problems/product-of-array-except-self/discuss/65789/Super-easy-(Java)-solution-in-O(N)-time-and-O(1)-space
- leftMult,rightMult 곱셈방향까지 표현한 이름이네.
- runnigtprefix , runningsurfix : 문제와 같은 단어 씀. 단어는 길지만 내용을 잘 나타낸다.
- https://leetcode.com/problems/product-of-array-except-self/discuss/65789/Super-easy-(Java)-solution-in-O(N)-time-and-O(1)-space
- 다른 사람 솔루션 보고 로직 개선해보기 || 다른 알고리즘 있다면 그걸로 풀어보기
- 위 로직대로 할 떄 비어있는 값을 어떻게 초기값으로 처리해주는지 그 방법이 다르고 나머지는 로직이 비슷해보인다.
- leetcode 구성 튜토리얼 안내 보기 - leetcode submission 무슨 소리인지 모르겠다.
- 제출한 솔루션들 중에 어디에 위치해있는지 알려주는 것임. 좋네. https://leetcode.com/submissions/detail/457229626/
회고 - 개선 필요점
- 경계값 테스트하기
- for statement 의 initial value 를 다르게 잡아서 if 문이 추가로 필요했음.
- 알고리즘에서 쓸 규칙적인 변수명 만들기
- 변수명이 왔다갔다해서 헷갈림. 좀 더 긴 솔루션에서는 내가 변수명에서 길 잃을듯. 변수명 만드는 것도 시간이 걸린다.
- 타임어택 방식 익숙해지기
- 1차 접근에서 로직은 맞는 거 같은데 당황해서 디버깅이 안됨. 타임어택이라 긴장함
- 개발 환경 미리 세팅하기 - 프로젝트 생성, 템플릿, 지우개 사기
- IDE - IDE 세팅하느라 오래 걸림. python 과 Java 둘 중 어떤게 쓰는게 편할지 몰라서 양쪽에 잡다보니 설정이 꼬임 → colab 으로
- 연필로 적는데 지우개가 없어서 메모가 더러워짐. → 샀다.
- 고민 → 결정 : 1차 접근 python 으로, 2차 다시 풀기는 Java도 함께 풀자.
- 어떤 언어로 풀지 미리 마음을 정해놓아야하나? python 이 문자열 처리에서는 편리함. 많은 데이터 케이스 처리할 때엔 Java 가 속도 이득
- python 이 battery-included 정책도 있어서 자료형 처리도 편하고, 변칙 유형에 유연하게 대응할 수 있다고 함.
- Java 가 약간의 속도 이득이 있을 수 있으니 둘 다 보기.