본문 바로가기

분류 전체보기267

[LeetCode] Max Consecutive Ones 파이썬 (문자열 압축) class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: local_max = 0 tmp = 0 for i in nums: if i == 1: tmp += 1 else: # print(local_max, tmp) local_max = max(local_max, tmp) tmp = 0 else: local_max = max(local_max, tmp) return local_max 주의점: loop가 정상적으로 순회한 후에도 max값이 update가 안되어있을 수 있기 때문에 for-else문을 통해 update 시켜줘야 한다. 카카오 문자열 압축 문제에서도 나온 유의사항. 다른 풀이는 class Solution(object): d.. 2021. 4. 29.
[LeetCode] License Key Formatting 파이썬 (str.replace) class Solution: def licenseKeyFormatting(self, s: str, k: int) -> str: tmp = [] s = s.replace("-","") s = s[::-1] for i in range(0,len(s),k): tmp.append(s[i:i+k]) # print(tmp) ans = "-".join([x[::-1] for x in tmp[::-1]]) return ans.upper() 조건 1. alphanumeric, dashes('-') 2. 정확히 k개의 char만큼씩 group으로 나누어야 함 2-1. 첫번째 group의 경우 1 2021. 4. 29.
[자료구조] 등굣길 파이썬 (DP) def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] # first row and colum are 1 for i in range(n+1): for j in range(m+1): if i == 1 or j == 1: dp[i][j] = 1 if i == 0 or j == 0: dp[i][j] = 0 if m 2021. 4. 26.
[자료구조] 빙고 파이썬 (hash,list comprehension) def solution(board, nums): n = len(board) # board의 길이 nums = dict.fromkeys(nums, True) # nums 리스트 값을 키로 변환하여 dict로 만들어준다, # nums = {14: True, 3: True, ... , 5: True, 15: True} row_list = [0] * n col_list = [0] * n left_diagonal = 0 right_diagonal = 0 for i in range(n): # O(n) for j in range(n): # O(n) if board[i][j] in nums: # O(1) board[i][j] = 0 # make it checked row_list[i] += 1 col_list[j] +.. 2021. 4. 26.
[gitignore] gitignore가 적용이 안될 경우 해결책 git rm -r --cached . git add . git commit -m "fixed untracked files" cached 지워주고 commit & push 하면된다. .gitignore가 작동하지 않을때 대처법 .gitignore가 제대로 작동되지 않아서 ignore처리된 파일이 자꾸 changes에 나올때가 있습니다. git의 캐시가 문제가 되는거라 아래 명령어로 캐시 내용을 전부 삭제후 다시 add All해서 커밋하시면 됩니 jojoldu.tistory.com 2021. 4. 25.
[자료구조] 야근 수당 파이썬 (heap) from heapq import heapify, heappush, heappop from collections import deque def solution(n, works): if n > sum(works): return 0 works = [(-i,i) for i in works] heapify(works) for _ in range(n): w = heappop(works)[1] - 1 heappush(works, (-w,w)) ################ # print works # while works: # w = heappop(works) # print(w) return sum(i[1]**2 for i in works) max value를 하나씩 -1 해줄 것이기 때문에 max heap를 구성해.. 2021. 4. 25.
[자료구조] 게임 아이템 파이썬 (heap, deque) 해답 from heapq import heapify, heappush, heappop from collections import deque def solution(healths, items): healths.sort() # 체력을 오름차순으로 정렬 items = sorted([(item[1], item[0], index+1) for index, item in enumerate(items)]) # 깎는 체력 순으로 정렬 items = deque(items) answer = [] heap = [] for health in healths: # 제일 작은 체력부터 루프 while items: # 아이템 루프 debuff, buff, index = items[0] # 가장 깎는 체력이 낮은 아이템 if healt.. 2021. 4. 25.
[자료구조] 방문 길이 파이썬 (hash) def solution(dirs): x,y = 5,5 # start point mapping = {"U":(0,1), "D":(0,-1), "R":(1,0), "L":(-1,0)} visited = [[0 for _ in range(11)] for _ in range(11)] for i,d in enumerate(dirs): if 0 2021. 4. 24.
[자료구조] FloodFill 파이썬 (BFS, queue) BFS from collections import deque def solution(n, m, image): cnt = 0 visited = [[False] * m for _ in range(n)] # visited table (col(m) x row(n)) dir = [[1,0], [0,1], [-1,0], [0,-1]] # 4-direction for i in range(n): for j in range(m): if not visited[i][j]: q = deque() # BFS-queue q.append([i,j]) visited[i][j] = True color = image[i][j] while q: x, y = q.popleft() for dx, dy in dir: xx, yy = x+dx,.. 2021. 4. 23.

티스토리툴바