공대생의 비망록

자료구조를 공부하게 되면 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..

주어진 두 문자열 s, t가 애너그램 (Anagram)인 지 판단하는 문제. 문제에서는 문자열 안에는 소문자만 포함된다고 하였으나 확장성을 고려하여 딕셔너리 (dictionary) 자료구조를 활용하여 푼 버전과 소문자 26개 (혹은 존재하는 소문자 수)만큼의 길이를 가지는 배열 (list)을 활용하여 푼 버전을 각각 구현해보았다: 딕셔너리 활용 버전:class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False dicts = {}; dictt = {} for ch in s: if ch not in dicts: ..

주어진 n에 대하여 0부터 n까지 "0" 혹은 "1"으로만 비트가 구성되어 있는 정수 (Monobit Integer)를 구하는 문제. 처음에는 모든 비트가 같아야 한다는 점에 착안, 0부터 n까지 모든 수를 비트 문자열로 만들어 XOR 비트 연산을 수행하여 문제를 해결하도록 구현하였으나 매우 비효율적이었고, 그 후로 초기 방법 (모든 수를 비트 문자열로 생성하여 XOR 연산):class Solution: def countMonobit(self, n: int) -> int: if n == 0: return 1 bitified = ["0"] for i in range(1, n + 1): m = i bit ..

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..