본문 바로가기

Coding Test/LeetCode57

[LeetCode] 937. Reorder Log Files [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (로그 파일 재정렬) 로그의 가장 앞부분은 식별자다. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 식별자는 순서에 영향을끼치지 않지만, 문자가 동일할 경우 식별자순으로 한다. 숫자 로그는 입력 순서대로 한다. 2. 풀이 람다와 + 연산자를 이용한 풀이 isdigit()을 이용해 숫자와 문자 로그를 구분한다. 람다를 통해 식별자가 아닌 로그 부분을 먼저 정렬 후 식별자를 정렬한다. letters.sort(key=lambda x: (x.split()[1:], x.split()[0])) 문자열 [1:]를 통해 정렬을 하고, 동일한 경우 후순위로 식별자 [0]로 정렬한다. + 연산자를 통해 문자와 숫자 로그를 합친다. .. 2021. 11. 23.
[LeetCode] 819. Most Common Word [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (가장 흔한 단어) 금지된 단어를 제외한 가장 흔하게 동장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉽표 등) 또한 무시한다. 2. 풀이 정규식과 해시를 이용한 풀이 정규식에서 \w는 단어 문자를 뜻하며, ^은 not을 의미한다. 따라서 re.sub(r'[^\w]', ' ', 문자열)는 단어 문자가 아닌 모든 문자를 공백으로 치환한다. defaultdict(int)를 통해 단어의 빈도수를 저장한다. max함수를 통해 딕셔너리의 값이 가장 큰 key를 출력한다. max(dic.keys(), key=lambda k: dic[k]) key=lambda k: dic[k.. 2021. 11. 23.
[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.

티스토리툴바