본문 바로가기
반응형

배열6

[LeetCode] 561. Array Partition I [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (배열 파티션 I) 2n개의 수를 가진 배열을 n개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. 2. 풀이 슬라이싱을 이용한 풀이 배열을 정렬한다. 정렬된 배열에서 짝수번째 항목을 더한다. 배열이 [1,4,3,2] 일 때, (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 이다. 슬라이싱 구문 [::2] 는 2칸씩 건너뛰므로 짝수번째 항목만 추출한다. 3. 코드 슬라이싱을 이용한 풀이 class Solution: def arrayPairSum(self, nums: List[int]) -> int: return sum(sorted(nums).. 2021. 11. 23.
[LeetCode] 238. Product of Array Except Self [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (자신을 제외한 배열의 곱) 배열을 입력받아 output[i] 가 자신을 제외한 나머지 요소의 곱셈 결과가 되도록 출력하라. *주의 : 나눗셈을 사용하지 않고 O(n) 에 풀어라. 2. 풀이 배열을 이용한 풀이 (출처) 자신을 제외한 왼쪽의 곱셈 결과를 넣는다. 자신을 제외한 오른쪽 곱셈 결과를 곱한다. 3. 코드 배열을 이용한 풀이 class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: ret = [] # 왼쪽 num = 1 for i in range(len(nums)): ret.append(num) num *= nums[i] # 오른쪽.. 2021. 11. 23.
[LeetCode] 121. Best Time to Buy and Sell Stock [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (주식을 사고팔기 가장 좋은 시점) 한 번의 거래로 낼 수 있는 최대 이익을 산출하라. 2. 풀이 배열을 이용한 풀이 최솟값을 계속 갱신하면서 현재값과 최솟값의 차이를 통해 최대 이익을 도출한다. 3. 코드 배열을 이용한 풀이 class Solution: def maxProfit(self, prices: List[int]) -> int: # 종료 조건 if len(prices) < 2: return 0 ret, minP = 0, 100000 for price in prices: if minP < price: ret = max(ret, price-minP) else: minP = price return ret 결과 :.. 2021. 11. 23.
[LeetCode] 42. Trapping Rain Water [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (빗물 트래핑) (출처) 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 2. 풀이 (출처) 위 그림처럼 최대 높이의 막대까지 각각 좌우 기둥 최대 높이와 현재 높이와의 차이만큼 물 높이를 더해 나간다. 스택을 이용한 풀이 (출처) 위 그림처럼 높아질 경우 변경된 높이만큼 물을 추가한다. 3. 코드 투 포인터를 이용한 풀이 class Solution: def trap(self, height: List[int]) -> int: # 종료 조건 if not height: return 0 ret = 0 left, right = 0, len(height)-1 left_max, right_max = he.. 2021. 11. 23.
[LeetCode] 15. 3Sum [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (세 수의 합) 배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. (중복된 엘리먼트 조합은 제외!!) 2. 풀이 투 포인터를 이용한 풀이 (출처) 오름차순으로 정렬 for문을 통해 (해당 value, 다음 value, 마지막 value) 3개의 합을 계산한다. 합이 0보다 크면 다음 value를 오른쪽으로 한칸 이동 합이 0보다 작으면 마지막 value를 왼쪽으로 한칸 이동 value가 이전값과 중복될 경우 continue 3. 코드 투 포인터를 이용한 풀이 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: ret =.. 2021. 11. 23.
[LeetCode] 1. Two Sum [Python(파이썬), JAVA(자바)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (두 수의 합) 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 2. 풀이 해시를 이용한 풀이 3. 코드 (Python) 해시를 이용한 풀이 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dic = {} for idx, val in enumerate(nums): num = target - val if num in dic: return [dic[num], idx] else: dic[val] = idx 결과 : 방식 Status Runtime Memory Language 해시 [Accepted] 60 ms 15... 2021. 11. 23.
반응형

티스토리툴바