n 개의 페어를 이용한 min(a,b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. 보면 이해가 안가는 문구이지만, 예제를 보고 이해하였다. 2n 개의 원소가 주어지는데 이를 n개의 min(a,b) 페어로 만든 후 그 페어들의 합이 가장 큰 경우를 출력하라는 뜻이다. 이를 해결하는 방법은 아주 간단하다. 배열을 작은 수 부터 정렬하는 것이다. 그렇게 하면 앞에서 부터 2개씩 끊었을 때, 최소 값이 더 작아지는 것을 막을 수 있다. 전체 코드는 다음과 같다. class Solution: def arrayPairSum(self, nums: List[int]) -> int: nums.sort() answer = 0 for i in range(0, len(nums), 2): answer += nums[i] ..

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. 이 또한 모든 경우의 수를 계산하면 n의 3승으로 매우 오래 걸린다. 그래서 이 문제도 투포인터로 해결한다. 먼저 배열을 정렬한다. nums.sort() 그 다음, 각 원소마다 for문을 돌며 3수의 합을 찾는다. for i in range(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: continue i 가 i-1과 같다면 같은 결과가 나올 것이기에 이는 넘어가주는 조건문을 작성한다. left, right = i+1, len(nums)-1 while left < right: sum = nums[i] + nums[left] + nums[right] if sum == 0: result = [nu..

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 이 문제는 투 포인터를 사용하여 해결한다. 투 포인터는 2개의 포인터를 가지고 리스트에 접근하는 알고리즘이다. 보통 조건에 따라 좌/우 포인터를 조작하고 그 행위를 좌측 포인터가 우측 포인터를 넘어갈 때 종료하는 식으로 접근하였던 것 같다. 이 문제 또한 이러한 매커니즘으로 접근해본다. 먼저 설정하는 조건은 다음과 같다. 왼쪽에서 설정한 left_max 값이 오른쪽에서 설정한 right_max 값 보다 낮으면 right를 가운데로 당겨오고, 그렇지 않으면 left를 가운데로 당겨가는 식이다. 먼저, left/right 포인터와 초기 left_max/right_max 값을 설정한다. volume = 0 left, right = 0, l..

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 처음 이 문제를 접하게 되면, 모든 경우의 수에 대한 조사를 할 것이다. 나 또한 그렇게 해결하였지만 이는 n의 제곱의 경우의 수로 매우 비효율 적이다. 그래서 파이썬으로 이러한 최적화 문제를 풀 때 가장 유용한 것은 딕셔너리를 이용하는 것이다. 예를들어 [2,3,7] 에서 3이라는 값이나 인덱스를 찾으려면 in이나 index 함수를 사용하여야 하는데 이는 O(n)이다. 하지만 이를 딕셔너리로 변환하여 'Dict[값] = 인덱스' 형태로 저장하면 해당 값의 인덱스를 찾거나, 해당 값이 있는지 확인하는데 걸리는 시간은 O(1)이 된다. 이를 활용하여 이 문제를 해결해보자. 먼저, 딕셔너리 형태로 배열을 정리한다. num_dict = {} ..

가장 긴 팰린드롬 부분 문자열을 출력하라. 팰린드롬을 확인할 문자열은 짝수 길이의 문자열, 홀수 길이의 문자열 2가지 종류가 있다. 그 전에 먼저 문자열에서 가장 긴 팰린드롬 문자열을 뽑는 함수를 만든다. def expand(left: int, right: int, s: str) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left+1:right] left와 right를 좌우로 한칸씩 늘려가며 확인한다. 만약 처음부터 while 조건에 맞지 않는다면, s[left+1:right]를 return 한다. 그리고 문자열 처음부터 2칸, 3칸 문자로 잘라서 expand함수로 가장 큰..

문자열 배열을 받아 애너그램 단위로 그룹핑하라. 애너그램은 문자열을 재배열해서 다른 문자로 만드는 것이다. 문제에서 말하는 애너그램 단위는 문자열 위치를 재배열하면 같은 문자가 되는 그룹들을 말하는 것이다. 먼저, 문자열을 정렬하여 딕셔너리 key로 생성 후 값을 빈 리스트로 초기화한다. for s in strs: ana = list(s) ana.sort() ana = ''.join(ana) if result.get(ana) == None: result[ana] = [] 그 다음 원래 문자열을 해당 키의 배열에 추가한다. result[ana].append(s) 전체 코드는 다음과 같다. class Solution: def groupAnagrams(self, strs: List[str]) -> List[L..