공대생의 비망록

투 포인터를 사용해서 푸는 대표적인 문제이다. 풀이:class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left = 0; right = len(numbers) - 1 while left

자료구조를 공부하게 되면 Stack의 특성을 활용하도록 꼭 한번은 경험하게 되는 문제를 LeetCode 플랫폼에서도 풀게 되었다.기존에는 C나 C++, Java로 구현했었는데 이번에는 Python으로 여러 방법을 구현해보았다. if-else 구문을 떡칠해서 문제를 해결하는 가장 기본적인 (멍청한) 방식:class Solution: def isValid(self, s: str) -> bool: stack = list() for ch in s: if ch == '(' or ch == '{' or ch == '[': stack.append(ch) elif ch == ')': if len(..

주어진 문자열 배열 strs에 대하여, 가장 긴 공통문자열을 찾는 문제.예를 들어 "flower", "flow", "flight" 문자열들이 주어졌다면 "fl"을 찾아 반환해야 한다. 문제 풀이:class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: length = 201 # Since the max length for this problem is 200. # length = min(len(w) for w in strs) # Pythonic way for s in strs: # set var length as the shortest string's length. if le..

영어 대소문자와 공백, 특수문자가 섞여 있는 문자열에서 영어 소문자만 가지고 회문 여부를 검증하는 문제.실제로 요구하는 대로 소문자만 존재하는 문자열로 가공하여 회문 여부를 검증하는 방법과 주어진 문자열 그대로 투 포인터를 사용하여 문제를 해결하는 방법을 각각 구현해보았습니다. 문자열 가공 후 회문을 판단하는 방법:class Solution: def isPalindrome(self, s: str) -> bool: lower = s.lower() trimmed = str() for ch in lower: if ch.islower() or ch.isdigit(): trimmed += ch for i in r..

주어진 문자열 s에서 첫 번째의 고유 문자 위치를 찾아 반환하는 문제.문자열을 1회차로 순회하며 dictionary 자료구조에 모든 문자의 빈도를 저장하도록 하고, 2회차로 순회할 때 dictionary에 빈도가 1이라면 그 위치를 반환하도록 하여 문제를 해결하였다. 문제 풀이 (시간복잡도는 O(n)이다.):class Solution: def firstUniqChar(self, s: str) -> int: seen = {} for i in range(len(s)): if s[i] not in seen: seen[s[i]] = 1 else: seen[s[i]] += 1 f..

set으로 만들어서 고유한 숫자만 남겨 sum을 2배로 하여 nums의 sum 값과 차감하여 숫자를 찾아내는 풀이:class Solution: def singleNumber(self, nums: List[int]) -> int: mySum = sum(set(nums)) * 2 diff = mySum - sum(nums) return diff XOR 비트 연산으로 배열을 순회하여 숫자를 찾아내는 풀이: (연달아 XOR 비트 연산으로 풀 수 있는 문제를 만나 습득하게 되었습니다.)class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for num in nums:..

이 문제는 보자마자 Python에 익숙한 사람이라면 누구나 쉽게 풀 수 있는 문제라는 생각이 들었다. for-loop을 통해 0부터 n까지 하나씩 확인하는 방법: (시간복잡도 O(n)이나 비효율적인 편)class Solution: def missingNumber(self, nums: List[int]) -> int: for i in range(len(nums) + 1): if i not in nums: return i set을 사용하며 쉽고 빠르게 문제를 해결하는 방법:class Solution: def missingNumber(self, nums: List[int]) -> int: comp = set(range(len(n..

멍청한 풀이: 시간복잡도 O(n^2)class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i = len(nums) - 1; j = 0; zeros = 0; moved = 0 while i >= 0: if nums[i] != 0: zeros += 1 i -= 1 else: if zeros == 0: # if there's 0 at the end of th..