class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res =[] s=[] v ={i: False for i in nums} def dfs(): if len(s)==len(nums): res.append(s[:]) return else: for i in nums: if not v[i]: s.append(i) v[i] = True ..

스도쿠 판이 주어지고 valid 한지 검증하는 방법처음에는 row, col, 한칸씩 for 계속 돌리는 방법을 생각했었는데 한번의 이중 for로도 해결할 수 있다class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: n = len(board) s = set() s2 = set() check = [[[] for _ in range(3)] for _ in range(3)] for i in range(n): s = set() s2 = set() for j in range(n): if ..

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightfrom collections import dequeclass Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None # right = self.invertTree(root.right..

import sysclass Solution: def maxProfit(self, prices: List[int]) -> int: minVal = sys.maxsize res=0 for i in prices: if i 엊그제인가 코테를 봤는데 1번 문제가 이거랑 똑같은 게 나왔다아주 쉬운 문제인데 1시간에 3문제라 촉박해서 그런지... O(n^2)으로 풀어버렸다실수하지 않게 다시 풀어본다...다행히도 1번을 O(n^2)으로 풀어내고 2, 3번엔 집중했는지,,, 코테는 붙어서 면접을 보게 됐다

class Solution: def removeDuplicates(self, nums: List[int]) -> int: s = set() res=0 i=0 for _ in range(len(nums)): if nums[i] in s: del nums[i] else: res+=1 s.add(nums[i]) i+=1 return res 이미 sorted 된 array 이기 때문에 이전 값과 비교하면 set을 안 써도 되어서 공간복잡도를 더 줄일 수 있겠다in-place 로 줄여야 해서.. del..

"""# Definition for a Node.class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random"""class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': v = {} def makeNode(curr): if not curr: return None if curr in v:..

처음에 bfs와 딕셔너리 쓰면 되는 건 잘 알겠는데, 어떻게 한글자씩 다른 word를 탐방할지 고민스러웠다for 문을 다 돌려서 딕셔너리에 넣고 비교하는 코드를 짰는데, 당연하게도 TLE 가 났고 ...답은 fox 면 그 안에 fix, fux, xox 이런 걸 넣는 게 아니라*ox : foxf*x: foxfo*: fox이렇게 딕셔너리에 키랑 값을 저장하는 거였다메모리는 많이 들겠지만 TLE 가 나지는 않을 것 같다from collections import Counter, defaultdict, dequeclass Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if end..

54. Spiral Matrix흔한 달팽이 문제다며칠 전에 본 기업 코테에서도 변형 달팽이 문제가 나왔는데 잘 알아두면 좋을 것 같다1. 방문 배열을 이용하는 방법,2. 세로길이 가로길이 세가면서 방향 턴 하는 방법정도가 있을 것 같은데 하나하나 조건 걸기 귀찮아서 1번으로 풀이했다.방향 바꾸는 조건 작성에서 실수하지 않는 게 중요하다. 특히 dxdy는 오타 한번 내면 찾을 수가 없다...class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: def change_dir(x): return (x+1)%4 dx,dy=[1,0,-1,0],[0,1,0,-1] ..

994. Rotting Oranges 쉬운 bfs 문제백준 토마토들을 열심히 풀었다면 10분컷할 수 있다연결된 오렌지 군집에 여러 썩은 오렌지가 있는 경우만 조심해서 큐에 미리 넣어주면 된다from collections import dequeclass Solution: def orangesRotting(self, grid: List[List[int]]) -> int: n,m = len(grid), len(grid[0]) v = [[-1]*m for _ in range(n)] dirx, diry=[0,0,-1,1],[-1,1,0,0] q = deque() for i in range(n): for j in range(m)..

브루트포스class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) res=[] def check (i,j): start = i end = j-1 while start dpclass Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[0]*n for _ in range(n)] ans = [0,0] for i in range(n): dp[i][i] = 1 for i in ran..