archives

2024 https://leetcode.com/problems/maximize-the-confusion-of-an-exam/ 바로 앞글의 1004번 문제랑 똑같다. 근데 이번엔 T나 F의 최대값으로 만들어야 한다. 그러면 간단하게는 T일경우의 최댓값과 F일경우의 최댓값을 구해서 그중에 최댓값을 리턴하면 된다. class Solution: def maxConsecutiveAnswers(self, ans: str, k: int) -> int: #ans = 'TFFT' #k = 1 l,r = 0,0 d = {'T':0, 'F':0} ret = 0 while r k and d['F'] > k: # l과 r사이, 즉 ..

이전에 이거 관련해서 글을 썼었는데.. 너무 뒤죽박죽한 글 구성 + 잘 모르는데 여기저기서 이상하게 갖다붙힘 + 버전이 낮아짐에 따라 쓸모 없어진 글이 되버려서 이전 글은 삭제하고 다시 좀 다듬어서 정리합니다. 현재 쓰고있는 spark 3 버전 초반 기준입니다. 1. mongodb 공식 api : https://docs.mongodb.com/spark-connector/current/python-api/ 몽고디비에서 데이터를 읽는 예시를 예로 듦. https://docs.mongodb.com/spark-connector/current/python/read-from-mongodb/ 공식 홈페이지에 코드 예제가 있는데.. pipeline = "{'$match': {'type': 'apple'}}" df = ..

935 https://leetcode.com/problems/knight-dialer/ 미리 다음에 갈수 있는 길들을 저장해놓는다. 그리고 n번만큼 반복해주면서 메모이제이션으로 한번 했던 계산은 하지 않도록 조절한다. class Solution: def knightDialer(self, n: int) -> int: #n=3131 d = {-1: range(10), 0: [4,6], 1: [6,8], 2: [7,9], 3: [4,8], 4: [0,3,9], 5: [], 6: [0,1,7], 7: [2,6], 8: [1,3], 9: [2,4]} cache = {} def dp(n, path): if n == 0: return 1 key = (n, path) if key in cache: return cach..

1405 https://leetcode.com/problems/longest-happy-string/ 단순히 dfs로 짜면 시간초과가 나왔다. 더 효율적으로 생각해보다가 가장 긴 길이를 만들어내려면 현재 존재하는 a,b,c중에서 가장 많이 존재하는 단어를 먼저 사용하는 전략으로 결과값을 만들어야 한다. 단어와 단어 카운트를 기반으로 힙을 만들어준 후 남아있는 단어중 갯수가 가장 많이 남아있는것부터 빼서 계산하는식으로 처리한다. from heapq import * class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: s = '' while a > 0 or b > 0 or c > 0: heap = [] if a > 0 a..

39 https://leetcode.com/problems/combination-sum/ 별다른 설명이 필요 없다. 백트래킹 연습용으로 좋은 문제다. class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: #candidates = [1,2] #target = 4 ret = [] def get_comb(candidates, cand, target): if target == 0: ret.append(cand) return for i in range(len(candidates)): if target-candidates[i] >=0: get_comb(candidates[i:], cand + [c..

1209 https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/ 딱봐도 스택문제다. 새 문자가 들어올때마다 새 문자와, 새 문자가 존재하는 갯수를 넣어두고, 동일한 문자가 들어오면 카운트를 증가시켜준다. 이후 마지막 문자가 k보다 큰 경우 연산을 해준다. class Solution: def removeDuplicates(self, s: str, k: int) -> str: #s = "deeedbbcccbdaa" #k = 3 ret = '' stack = [] for i in range(len(s)): if stack and s[i] == stack[-1][0]: # 이미 들어왔던 문자의 경우 카운트를 늘려준다. stack[-1..

244 https://leetcode.com/problems/shortest-word-distance-ii/ 모든 word의 인덱스를 저장해놓는다. 그리고 구해야 하는 두 점에 대해서 투 포인터로 가장 근접해 있는 점 끼리의 최소값을 업데이트해준다. class WordDistance: def __init__(self, wd: List[str]): self.d = {} for i, w in enumerate(wd): self.d[w] = self.d.get(w, []) + [i] #print(self.d) def shortest(self, w1: str, w2: str) -> int: ret = 9999999999 i,j = 0,0 d1,d2 = self.d[w1],self.d[w2] while i < l..

227 https://leetcode.com/problems/basic-calculator-ii/ 이전 부호의 상태값을 저장해놨다가 그걸 기반으로 푼다. 이런 계산기반의 문제는 보통 부호를 한번 저장해놓고 다음단계에 가져와서 쓰는식으로 하는것 같다. 하드문제인 https://leetcode.com/problems/basic-calculator/ 와 비교해보면서 익히자. class Solution: def calculate(self, s: str) -> int: num = 0 stack = [] sign = '+' i = 0 while i < len(s): #print(s[i],stack) if s[i].isdigit(): num = num * 10 + int(s[i]) if s[i] in '+-*/' o..

1762 https://leetcode.com/problems/buildings-with-an-ocean-view/ 왼쪽에서부터 검사하면 오른쪽에 높은 벽이 나타났을때 다시 왼쪽의 케이스를 체크해야한다. 그런데 오른쪽에서부터 왼쪽으로 가면서 하면 다시 오른쪽의 케이스를 체크할 필요가 없다. 오른쪽에서 왼쪽으로 가면서, 최대값을 유지해주고 현재까지의 최대 높이보다 높아지는 왼쪽 높이가 나오면 그 인덱스를 저장해두면 된다. class Solution: def findBuildings(self, h: List[int]) -> List[int]: cur_max = 0 ret = [] for i in range(len(h)-1, -1, -1): if h[i] > cur_max: ret.append(i) cur_m..

986 https://leetcode.com/problems/interval-list-intersections/ 왠지 그리디 문제같이 생긴 list intersection문제이다. 무식하게 풀면 안되고 규칙을 찾은 뒤에 구현하면 된다. 투 포인터를 쓰기는 하는데 그냥 구현하면 된다.. 두개의 리스트가 있을때 겹치는 경우는 first_start List[List[int]]: diagonal_dict = {} for i in range(len(mat)): for j in range(len(mat[0])): if i-j not in diagonal_dict: diagonal_dict[i-j] = [] diagonal_dict[i-j].append(mat[i][j]) #for k,v in diagonal_dic..