처음에 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..

처음 보는 플랫폼이다import sysinput = sys.stdin.readlinen, k = map(int, input().split())s = list(map(int, input().split()))for i in range(1, n): s[i] += s[i-1]for _ in range(k): a, b = map(int, input().split()) a-=1 b-=1 c=0 if a-1 >=0: c = s[a-1] print (round((s[b]-c)/(b-a+1),2))간단하게 누적합으로 풀었다

253. Meeting Rooms II

처음에 bfs로 풀었다가 크게 당했던 문제...다 풀고나서 통과 못한 테케를 보고 백트래킹 써야하는 걸 깨달았다class Solution: def exist(self, board: List[List[str]], word: str) -> bool: n,m = len(board), len(board[0]) dirx,diry=[0,0,-1,1],[1,-1,0,0] start=[] for i in range(n): for j in range(m): if board[i][j] == word[0]: start.append((j,i)) def backtrack(x,y,s..

위상정렬이 med로 나오다니 무서운 곳이다옛날에 열심히 연습했던 것 같은데 오랜만에 보고 1트로 풀어서 뿌듯deg 가 0인 것부터 진입할 수 있다from collections import dequeclass Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 위상정렬 r = {i: 0 for i in range(numCourses)} link = {i:[] for i in range(numCourses)} fin =[] q = deque() for pre, cur in prerequisites: r..

First Try: TLEI was like.. why does it make TLE???? it seemed like there was only one for loopHOwever "if i not in nums:" also takes O(n).. which makes the Time Comp O(n^2)Even so it needs some optimizationIn the for loop, we only have to iter till the length of the list, and if theres no return value then return n+1class Solution: def firstMissingPositive(self, nums: List[int]) -> int: ..

easy Q that asks the missing numberclass Solution: # 0~n 까지인 배열/set/dict를 만들고, nums 에 for 돌리면서 없는지 찾기 def missingNumber(self, nums: List[int]) -> int: # for no in range(len(nums)+1): # if no not in nums: # return no n = len(nums) ex_res = (n*(n+1))//2 tmp = sum(nums) return ex_res-tmp At first attempt...came up with a common ans,..