Scribbling

class TrieNode: def __init__(self): self.children = {} self.endFlag = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.endFlag = True def search(self, word: str) -> bool: node = self.root for char in word: if char not i..

class Solution: def singleNumber(self, nums: List[int]) -> int: num = nums[0] for i in range(1, len(nums)): num ^= nums[i] return num

단순 구현 문제로 생각했는데, 시간 초과가 발생한다. 메모리를 더 써서 시간을 줄여야 한다. class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: m, n = len(board), len(board[0]) ret = [] for word in words: found_flag = False for i in range(m): for j in range(n): if board[i][j] == word[0]: visited = [[False] * n for _ in range(m)] visited[i][j] = True if self.dfs(board, visited, i, j, word[1:]): r..

위상 정렬 문제다. result의 길이를 통해 위상 정렬 성공 여부를 파악 가능하다. class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: indegrees = [0] * numCourses graph = [[] for _ in range(numCourses)] for v, u in prerequisites: graph[u].append(v) indegrees[v] += 1 ret = [] q = [] for node, indegree in enumerate(indegrees): if indegree == 0: q.append(node) while q: u = q.pop() ret...

척보면 binary search 문제이다. class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: max_capacity = 0 for w in weights: max_capacity += w ret = max_capacity l, r = 0, max_capacity while l capacity: num_days += 1 tempsum = w return (num_days

"Eratosthenes Algorithm"을 사용한다. class Solution: def countPrimes(self, n: int) -> int: if n

DP 기초 문제로 맨날 보는 문제 class Solution: def rob(self, nums: List[int]) -> int: if len(nums)

프로그래머스에도 있는 문제이다. 문제를 처음 봤을 때, 가장 먼저 nums를 정렬해야된다는 것을 알 것이다. 여기서 정렬을 어떻게 하는지가 핵심인데, 34343 과 3434 중 어느것이 먼저 나와야할지를 생각해보면 된다. 그냥 정렬한다면, 34343이 앞에 와버리는 문제가 있다. 34343+3434 반대의 경우는, 3434+34343 그러나 후자의 경우가 더 크다. 이를 검출할 수 있는 방법은 해당 숫자들을 반복시켜서 얻는 새로운 숫자열을 비교하는 것이다. 3434334343과 34343434 를 비교하면 된다. 아래 코드에서는 숫자를 10번 반복시키는데, 이는 숫자의 최대 길이가 10이기 때문이다. (1과 10000000000의 비교하는 경우) class Solution: def largestNumbe..

알고리즘 문제라고 하기도 애매한 것 같다. n! 결과값에서 맨 뒤에 놓이는 0의 갯수를 찾는 문제이다. 맨 뒤의 0의 갯수는 n!으로 만들 수 있는 10의 갯수와 동일한데, 10은 2*5이므로, 2*5가 몇 번 발생하는지 확인하면 된다. 2*5의 횟수는 다시 5의 횟수로 결정된다. (2는 흔하니까) class Solution: def trailingZeroes(self, n: int) -> int: ret = 0 x = 5 while n >= x: ret += n // x x *= 5 return ret

O(1) Memory로 어떻게 풀지 고민해보았다. 방법은 두 List의 node 갯수를 파악하는 것이다. # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: m, n = 0, 0 cur = headA while cur != None: m += 1 cur = cur.next cur = headB while cur != None: n += 1 cur = cur.next if m >= n: for..