접근 주어진 문자열의 각 문자를 결과 문자열(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으로 뒤에 있는 문자열을 날리는 방법으로 풀어야 한다. ...
접근 가능한 속도 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
사고 같은 크기의 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 개를 가지는 하나의 케이스라고 생각했다. 그래서 모든 경우의 수를 수도코드로 생각하고 아래와 같이 구현했다. ...
접근 dp 는 s의 현재 index를 단어의 끝으로 가장 길게 완성할 수 있는 시작 index를 가리킨다. 각 스트링 인덱스 i 마다 0부터 i까지 loop 돌며 딕셔너리에 있는지 확인한다. 딕셔너리에 있다면 그 앞선 단어와 연결되는지 확인 후 dp 업데이트 한다. i-5 ~ i 까지 이어지는 단어가 있다면 ?? ~ i-6 까지 이어진 단어가 있는지 보는식이다. 사고 처음에 dfs 로 접근하였다. 시간초과를 받고 dp 로 다시 풀었다. 시간 복잡도 O(s.length ^ 2) ...
접근 linear 로 훝으며 모든 값을 곱하며 진행한다. 메모리 절약을 위해 부호만 기록한다. 각 index 에서 여태의 곱연산 부호에 따라 조건부로 최대 부분 수열 길이를 갱신한다. 0 을 만나면 필요한 변수들 초기화한다. 사고 0은 처리해줘야 하고, 양수는 곱해져도 어딜 slicing 하는지에 따라 부호가 바뀌지 않는다. 따라서 0이 아닌 값들을 쭉 이어서 길이를 기억한다. 첫번재 음수가 나오는 인덱스를 표시해놓고 현재 pointer 까지 곱연산이 양수이면 현재 까지 이어진 값의 길이와 max 를 비교해서 값을 갱신하고 음수라면 (pointer - 첫번째 음수 인덱스) 와 max 를 비교하여 갱신한다. ...
접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach, 점프 횟수 카운트, 새로운 reach 후보 변수인 temp 네 가지 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 index 를 temp 후보와 비교해 업데이트 한다. 이제 점프할 차례 때 가장 큰 temp 값을 보장해주는 곳으로 점프하고 이전 pointer에 이어서 후보군을 탐색한다. 지금까지 본 곳 중에서는 지금 자리가 가장 멀리까지 갈 수 있다는 사실을 알기 때문이다. 따라서 pointer 가 linear 로 진행하는 것이 곧 시간복잡도 O(n) 이 되며 최적해이다. 사고 앞선 Jump Game 과 다른 점은 reach 를 계속 업데이트 하지 않고 후보군을 끝까지 탐색 후 jump++ 와 reach 변수 재지정이 이루어지는 것이다. 그렇게 뜨문 뜨문 갱신되는 reach 내에서 loop를 반복적으로 돌아준다. ...
접근 현재 pointer 와 닿을 수 있는 최대 거리인 reach 두 변수를 이용한다. 닿는 index 중 가장 멀리까지 갈 수 있는 reach 로 계속해서 업데이트 한다. reach 만 max 를 이용해 업데이트하고 pointer 는 linear 로 움직인다 O(n). 사고 먼저 최대거리로 포인터를 옮기고 진행이 불가능하면 하나씩 뒤로 무르는 backtracking 이 떠올랐다. 하지만 visit 을 체크하는 과정에서 비효율적이라는 생각이 들어 기각했다. class Solution: def canJump(self, nums: list[int]) -> bool: pointer = 0 reach = nums[pointer] if reach + 1 >= len(nums): return True while pointer < reach: pointer += 1 reach = max(reach, pointer + nums[pointer]) if reach + 1 >= len(nums): return True return False
접근 처음과 마지막이 접하기 때문에 House Robber I 과 다른 방식을 생각해야한다. 첫번째 집을 털면 마지막 집은 고려할 필요가 없다. 그래서 0, len(배열) - 1 과 1, len(배열) 로 자른 두개의 배열에 단순하게 접근하면 된다. 사고 한참 예전에 이와 비슷한 cycle 이 있는 배열 dp 문제를 풀었는데 그보다 시간이 지난 뒤에 못 풀어서 당황했던 기억이 있다. 그 당시엔 아마 배열 마지막 집 전까지 dp 업데이트 후 첫번째 집과 마지막 집 value 를 비교했던것 같은데, 위험한 접근이고 edge case 도 매우 많았을 거라 생각된다. ...
접근, 사고 확실히 푼 문제 수가 쌓일수록 유형별로 나눠서 생각하기가 수월한것 같다. 이 유형의 베이스는 Two Sum 이다 (무려 리트코드의 첫번째 문제!!). 배열을 탐색하며 두 개의 합의 target 이 되는 쌍을 찾는 문제인데 해쉬를 이용해 한 번 linear 로 훑는 것으로 풀 수 있다. 대략적인 풀이과정은 set 선언 배열 지나가며 각각 원소 i에 대해 target - i 가 set 에 있으면 해당 쌍 리턴, 없으면 set.add(i) 해준다. 본 문제도 이와 크게 다르지 않다. ...