굿

Problem) Solution 1) 2중 for문을 사용해서 인덱스 i + j 값을 활용하여 리스트의 대각선 성분들끼리 묶을 수 있습니다. 예제의 경우 각 위치의 i + j 값은, [[1, 2, 3], [[0, 1, 2], [4, 5, 6], ----> [1, 2, 3], [7, 8, 9]] [2, 3, 4]] 이와 같이 표현할 수 있기 때문에 O(n)의 복잡도로 모든 원소들을 대각선 묶음으로 저장해서 얻은 딕셔너리를 각 키 값의 성분들을 역순으로 출력하면 원하는 값을 얻을 수 있습니다. d = {"0": [0], "1": [2, 4], "2": [3, 5, 7], "3": [6, 8], "4": [9]} 각 리스트들의 역순 reversed_d = {"0": [0], "1": [4, 2], "2": [..

Problem) Solution) class Solution: def arrayPairSum(self, nums: List[int]) -> int: return sum(sorted(nums)[::2])

Problem) Solution) 쉬워 보이지만 제대로된 풀이법을 생각해 내는데 꾀 오랜 시간이 걸렸다.. 계속해서 무식한 방법을 사용하다 보니까 시간 초과가 나서... leetcode 사이트에 discussion에 좋은 설명이 있어서 참조하여 설명글을 정리하겠습니다. 기본 아이디어는 입력받은 리스트 값을 하나씩 단계별로 더해서 sum값을 구할 때, 이 sum값이 k만큼 증가하는 순간에 합이 k값인 subarray를 구할 수 있습니다. 무슨 의미인지 풀어서 설명하겠습니다. 리스트 [1, 2, 1, 3]과 k = 3이 주어진다면, 단계별 sum값들은 [1, 3, 4, 7]이 됩니다. 이때, 1 -> 4인 순간과 4 -> 7인 순간을 통해서 우리는 합이 3인 subarray가 2개 있다는 것을 알 수 있습니..

python에서 제공하는 표준 라이브러리인 bisect에 대해서 정리하겠습니다. bisect bisect는 이진 검색 알고리즘을 이용하여 입력받은 시퀀스를 검색하는 기능을 제공하는 함수 입니다. # bisect.bisect(a, x, lo=0, hi=len(a)) # 리스트 a에 x값이 들어갈 자리의 인덱스값을 반환합니다. temp = [1, 3, 4, 5] bisect.bisect(temp, 2) # 출력값 : 1 bisect_right, bisect_left bisect는 bisect_right와 동일하며, 이 두 함수는 리스트 a에 x와 동일한 값이 존재하면 해당 값의 뒷 인덱스 값을 반환합니다. bisect.bisect_right(temp, 3) # 출력값 : 2 하지만, bisect_left는 ..

Problem) Solution) 이전에 풀었던 "Container With Most Water"와 거의 유사한 문제입니다. 길이 n의 배열이 주어지고 배열의 각 값은 위 그림에 보이는 것 같이 'bar'의 길이를 나타냅니다. 이때, 비가 와서 물이 가득 찼을 때의 물의 양을 구하면 됩니다. 풀이법은 n 길이의 배열을 for loop으로 돌리면서 각 단계마다 중심 기둥이 되는 위치의 좌측에서 가장 높은 기둥을 "left", 그리고 우측에서 가장 높은 기둥 "right"라고 정의 합니다. 이때, left와 right중 작은 기둥의 높이 만큼 빗물이 찰 수 있게 되고 따라서 얻은 작은 기둥의 높이에서 중심 기중의 높이의 차이가 실제로 해당 공간에 빗물이 찰 수 있는 공간이 됩니다. 설명이 조금 복잡해 보이는..

Problem) Solution) 먼저 제 첫번째 솔루션 입니다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for idx, value in enumerate(nums): if (target - value) in nums: if nums.index(target - value) != idx: return [idx, nums.index(target - value)] 그보다 x20 빠른 솔루션 입니다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: d = {} for i, n in enumerate(nums): m = targ..