LeetCode 1722 Minimize Hamming Distance After Swap Operations 접근 연결되어 있는 인덱스 정보를 담을 그래프 graph, 방문 여부 visited 를 초기화한다. iteration 돌면서 각 i 가 아직 방문 안했다면 bfs로 연결된 인덱스를 모두 찾는다. 연결된 인덱스를 lst 에 담고 subset 에는 해당하는 인덱스의 source 값을 담는다. bfs 가 끝나면 lst 의 모든 원소에 대해 target[i] 가 subset 에 있는지 찾는다. target[i] 가 subset 에 있다면 스왑으로 distance 를 0으로 만들 수 있으므로 총 거리에서 빼준다. 사고 swap 으로 자리를 바꿀 수 있는 원소들은 어떤 배열로든 만들 수 있다. 따라서 연결되어 있는 인덱스들로 그룹을 나누고, 특정 그룹의 원소들을 source 와 target 을 살펴서 source[i] == target[i] 여부를 확인할 수 있다. e.g. allowedSwaps =[[1, 2],[0, 2]] 라면 0, 1, 2 인덱스는 한 묶음이다. 이에 대해 target[i] (i = 0, 1, 2) == source[0] or source[1] or source[2] 라면 자리를 바꿔서 같은 원소를 놓을 수 있다는 뜻이므로 거리가 0이다. union-find 나 bfs 로 접근가능하다. ...

LeetCode 1011, Capacity To Ship Packages Within D Days 접근 binary-search 로 적절한 배의 weight 용량을 찾는다. 처음 lo, hi 는 max(weights), sum(weight) 이다. 각각 용량에서 옮기는데 걸리는 날짜를 계산해서, 총 날짜보다 적은 시간으로 옮겼으면 lower bound 를 올리고 아니라면 upper bound를 내린다. 사고 릿코드에 binary search 문제 정말 많다. 기본적으로 이런 유형의 최적값 찾기 binary search 는 lower, upper bound 사이에 조건 충족하는 값이 1개 이상 있다고 전제한다. 조건 days 가 5라면 직관적으로 5를 다 써서 옮기는 수 중에 최적이 있을거 같아보인다. 하지만 4일이나 3일만에 옮기고 그때의 배 용량이 최적일수도 있다. 어쨌거나 우리는 최소 날짜를 구하는게 아니라 최소 용량을 구하는거라 과정을 들여다보면 binary search 가 정말 아름답게 그 값을 찾는다는 것을 알 수 있다.. 문제의 조건을 차근차근 이해함에 따라 binary search 로 뭘 찾을지, bound 는 무엇이고 어떤 경우에 bound 를 어떻게 수정할지도 보인다. ...

접근 주어진 문자열의 각 문자를 결과 문자열(ans)에 추가한다. 만약 ans[-1] 이 폭발 문자열의 마지막 bomb[-1] 과 같다면 ans[-len(bomb):] 과 bomb[:] 을 비교하여 같으면 폭발시킨다. 사고 worst case time complexity 가 10**6 이길래 O(n) 으로 되는 문제인가 고민했다. 넉넉히 된다. 조건을 이해했을때 ‘모든 폭발 문자열이 폭발하고 새로운 문자열이 생긴다’ 여서 폭발 문자열을 발견할때마다 폭발하는거랑 결과가 혹시 다른가 고민해보았다. 반례가 떠오르지 않아 O(n) 스택으로 풀었다. 한가지 처음에 arr = arr[0:arr - len(bomb)] 이렇게 넣었다가 TLE 떴다. 저렇게 넣어도 파이썬이 optimization 하지 않을까 했는데 정직하게 주어진 인덱스만큼 복사하는것 같다. pop으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...

LeetCode 1146, Snapshot Array 접근 length 로 2차원 배열(arr)을 초기화한다. snap_id 를 기억하는 변수를 지정한다. 차지하게 되는 총 메모리는 length + S (number of calls of set()) 이다. set 마다 해당 index 에 현재 snap_id 와 value 를 추가한다. 모든 range 내의 i에 대하여 arr[i] 는 오름차순으로 정렬되어있기에 get() 에서 bisect 로 적절한 snap_id 를 찾아 해당하는 value 를 리턴한다. 사고 처음에 이 코드로 냈는데 get과 set 모두 엉성하다.. bisect에 대한 예쁜 이해가 없어서 그렇다. ...

접근 dictionary 에 키에 해당하는 리스트를 만들고 오름차순의 input 을 받는다. get 부를때 해당 키의 리스트에서 binary search 로 최댓값을 찾는다. 사고 평범한 binary search 문제이다. 문제 조건에서 들어오는 timestamp 는 오름차순으로 찍힌다고 하는게 큰 길잡이이다. from collections import defaultdict class TimeMap: dic = None def __init__(self): self.dic = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.dic[key].append([timestamp, value]) def get(self, key: str, timestamp: int) -> str: lo, hi = 0, len(self.dic) - 1 ans = "" while lo <= hi: mid = (lo + hi) // 2 if self.dic[key][mid][0] > timestamp: hi = mid - 1 else: ans = self.dic[key][mid][1] lo = mid + 1 return ans

접근 가능한 속도 1 과 10^7 사이에서 binary search 로 최소 속도를 찾는다. 각 속도마다 train list 를 돌며 걸리는 시간을 계산에서 binary search range 를 조정한다. 시간복잡도 O(Nlog10^7) 사고 적정값을 찾아야 되는 문제는 binary search 로 접근하는 경우가 많은거같다. 무난한 binary search 유형이다. import math class Solution: def minSpeedOnTime(self, dist: list[int], hour: float) -> int: lo, hi = 1, 10000000 minspeed = float('inf') while hi >= lo: mid = (hi + lo) // 2 timetook = 0 for i in range(len(dist) - 1): timetook += math.ceil(dist[i] / mid) timetook += dist[-1] / mid if timetook <= hour: minspeed = mid hi = mid - 1 else: lo = mid + 1 if minspeed == float('inf'): return -1 else: return minspeed

접근 정렬되어 있는 array 의 처음과 끝에 포인터를 둔다. target 과 비교하며 포인터를 움직인다. 사고 정렬되어 있고, 답이 하나로 보장되어 있다길래 two pointer 썼다. class Solution: def twoSum(self, numbers: list[int], target: int) -> list[int]: i, e = 0, len(numbers) - 1 while i < e: if numbers[i] + numbers[e] == target: return [i + 1, e + 1] elif numbers[i] + numbers[e] > target: e -= 1 else: i += 1

사고 같은 크기의 matrix 에 0, 0 부터 현재 index 까지 만들어지는 사각형 sum 을 저장하는 방식이 쉬우면서도 효율적인 접근이다. 왜인지 모르겠으나 불필요한 operation 이 포함된다고 생각해서 나는 같은 크기의 matrix 에 같은 row 에 있는 현재까지의 column sum 을 저장했다. 결론적으로 첫번째 접근보다 비효율적이다. 긴 row 에는 dp 에 여러번 접근해야할뿐더러 row 가 길수록 col1 을 빼주는 operation 을 많이 하게 된다. class NumMatrix: mat = None def __init__(self, matrix: list[list[int]]): self.mat = [[0] * len(matrix[0]) for _ in range(len(matrix))] for r in range(len(matrix)): self.mat[r][0] = matrix[r][0] for c in range(1, len(matrix[0])): self.mat[r][c] = self.mat[r][c - 1] + matrix[r][c] def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: blk = 0 for r in range(row1, row2 + 1): blk += self.mat[r][col2] blk -= self.mat[r][col1 - 1] if col1 > 0 else 0 return blk

접근 전체 node 가 head를 제외하고 n개일 때 head 에서 왼쪽에 k, 오른쪽에 n-k 만큼의 node를 갖는 경우의 수는 dp[k] * dp[n - k] 이다. 경우의 수를 곱해서 찾기 때문에 dp[0] 은 1로 둔다. 사고 예제 그림에서 보듯이 가능한 현재 경우의 수는 이전의 경우의 수 전체를 왼쪽 subtree, 오른쪽 subtree 로 갖는 경우로 생각해서 dp[i - 1] * 2 + ? 으로 시작했다. 이건 왼쪽에 dp[n - 1] 개, 오른쪽 0 그리고 오른쪽 dp[n - 1], 왼쪽 0 개를 가지는 하나의 케이스라고 생각했다. 그래서 모든 경우의 수를 수도코드로 생각하고 아래와 같이 구현했다. ...