본문 바로가기

분류 전체보기147

[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] 49. Group Anagrams [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (그룹 에너그램) 문자열 배열을 받아 애너그램 단위로 그룹핑하라. 애너그램이란 문자를 재배열하여 다른 뜻을 가진 단어로 바구는 것 (&#39;문전박대&#39; -> &#39;대박전문&#39;) 2. 풀이 해시 를 이용한 풀이 sorted()를 이용해 문자열 정렬 오름차순 sorted(arr) 내림차순 sorted(arr, reverse=True) defaultdict를 통해 애너그럼 그룹핑 3. 코드 해시를 이용한 풀이 from collections import defaultdict class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]].. 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] 5. Longest Palindromic Substring [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (가장 긴 팰린드롬 부분 문자열) 가장 긴 펠린드롬 부분 문자열을 출력하라. (정답이 여러개 일 수 있는데 나는 가장 첫번째 부분 문자열을 출력하겠다.) 2. 풀이 투 포인터를 이용한 풀이 (출처) 그림과 같이 2칸, 3칸으로 구성된 투 포인터를 슬라이딩 윈도우처럼 오른쪽으로 한칸씩 이동하며 팰린드롬을 확인한다. 3. 코드 class Solution: def longestPalindrome(self, s: str) -> str: # 팰린드롬 판별 및 포인터 확장 def expand(left, right): while left >= 0 and right 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.
[LeetCode] 344. Reverse String [Python(파이썬)] &#39;파이썬 알고리즘 인터뷰&#39;를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (문자열 뒤집기) 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며，리턴 없이 리스트 내부를 직접 조작하라. 2. 풀이 투 포인터를 이용한 풀이 reverse()를 이용한 문제 풀이 3. 코드 투 포인터를 이용한 풀이 class Solution: def reverseString(self, s: List[str]) -> None: left, right = 0, len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 reverse()를 이용한 풀이 class Solution: def reverseString(.. 2021. 11. 23.

티스토리툴바