Python

문제는 여기에서 볼 수 있다. 읽어보면 굉장히 간단한 문제임을 알 수 있지만, 생각보다 빠르게 실행되는 코드를 작성하기 어렵다. 문제에서는 O(log n)으로 구현해보길 권장하고 있다. 내 풀이 O(log n) 보자마자, 'Two-Pointer 문제인가?' 생각이 들었다. 그래서 아래와 같이 구현해봤다. def searchRange(self, nums: List[int], target: int) -> List[int]: result = [-1, -1] if not nums: return result if len(nums) == 1: if target == nums[0]: return [0, 0] else: return result left , right = 0, len(nums) - 1 while left

문제는 여기서 볼 수 있다. 간단히 설명하자면 여러 숫자가 포함되어 있는 배열이 주어지고, 해당 배열에서 세 개의 원소의 합이 0이 되는 경우의 수를 모두 찾는 것이다. 이것도 역시 예전에 풀어봤던 문제인데, 당시에는 브루트 포스로 풀어서 느린 성능을 보였다. 그리고 역시나 Discuss에서 굉장히 좋은 성능을 보이는 코드를 찾았었다. Discuss 코드를 보기 전에 스스로 풀어봤는데, 웬 걸! 그 코드와 같은 알고리즘을 생각해서 풀어냈다. 그런데 너무 코드가 길고 더러워서 블로그에는 예전에 찾았던 Discuss 코드를 남긴다. (분명 Discuss 어딘가에서 봤는데, 해당 글을 도저히 찾지 못하겠다 ㅠㅠ) 바로 코드 먼저 보자. class Solution: def threeSum(self, nums: ..

리트코드 문제를 풀던 중, 재밌는 현상을 발견해서 간단한 실험과 검색을 통해 알아낸 것을 짧게 적으려고 한다. 재밌는(?) 현상 LeetCode(리트코드)라는 코딩 테스트를 준비할 수 있는 알고리즘 문제 사이트에서 발견한 Two Sum이라는 아주 쉬운 문제였는데, 처음에는 아래와 같은 풀이를 작성했다. class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: nums_dict = {} for idx, num in enumerate(nums): remain = target - num if remain in nums_dict: return [nums_dict[remain], idx] nums_dict[num] = idx 그런데 ..