LeetCode

문제는 여기에서 볼 수 있다. 읽어보면 굉장히 간단한 문제임을 알 수 있지만, 생각보다 빠르게 실행되는 코드를 작성하기 어렵다. 문제에서는 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

문제는 여기에서 볼 수 있다. 문제 설명 문제를 간략하게 설명하자면, 입력으로 들어오는 숫자 배열과 하나의 target 숫자가 있고 target 숫자가 배열 안에 존재하면 해당 target이 위치한 인덱스를, 존재하지 않으면 -1을 return 하는 문제이다. 단, 입력되는 숫자 배열에 몇 가지 조건이 있는데 1. 배열 안의 모든 숫자는 중복되지 않는다. 2. 배열 안의 모든 숫자는 오름차순이지만, 아래 3번의 규칙을 따른다. 3. 배열 안의 숫자들은 특정 숫자(pivot)를 기준으로 rotate 되었다. 예를 들면, [0, 1, 2, 3]이라는 배열은 0이라는 숫자를 기준으로 [2, 3, 0, 1]처럼 rotate 될 수 있고, 1이라는 숫자를 기준으로 [1, 2, 3, 0]처럼 rotate 될 수 있..

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

이 문제도 반 년 전쯤에 풀었던 문제다. 복습 겸 내 풀이와 가장 빠른 풀이를 남겨본다. 문제는 여기에서 확인해보면 된다. 문제 설명 간단하게 문제를 설명하자면, 한 문자열에서 가장 긴 Palindrome을 찾는 것이다. 여기서 Palindrome이란, '회문'이라고도 불리며, 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 뜻한다. 예를 들면, 'abcba'나 'abba'는 Palindrome이라고 할 수 있다. Palindrome인지 확인하는 함수는 Two Pointer 방법이나, 파이썬에서는 [::-1]을 이용하면 쉽게 구현할 수 있다. 내 풀이 코드 먼저 보자. import re class Solution: def isPalindrome(self, s:str) -> bool: return s == s[..

문제는 여기에 들어가서 보면 된다. 무려 11개월 전에 풀었던 문제인데, 복습할 겸 글을 작성한다. 제출 기록들을 보니, 이때는 알고리즘 코딩을 많이 안 해봤을 때라 혼자 시도하다가 결국 discussions에서 풀이를 찾았던 것 같다. 그중 가장 빨랐던 풀이는 아래와 같다. class Solution(object): def lengthOfLongestSubstring(self, s): subs = {} start = max_length = 0 for i, x in enumerate(s): if x in subs: sums = subs[x] + 1 if sums > start: start = sums num = i - start + 1 if num > max_length: max_length = num ..

Top 100 Liked Questions 중 하나인 Word Search 풀이를 공유한다. 문제를 읽어보면 dfs로 풀어야 할 것 같은 느낌이 빡 오는 문제이다. 내 풀이 나는 board의 (0, 0)부터 (m-1, n-1)까지 하나씩 돌며 dfs를 사용했다. 그 과정에서 visited라는 board와 같은 크기의 boolean 값으로 이루어진 2차원 리스트를 두었다. 여차 저차 해서 구현한 나의 풀이는 아래와 같으며, 결과는~~ class Solution: def dfs(self, board, word, row_idx, col_idx, curr_string, visited): if len(curr_string) == len(word): if curr_string == word: return True ..