bereben

문제 문제는 어렵지 않다. 오름차순으로 정렬되어 있는 letters안에 target보다 큰 문자를 return, 만약 없다면 첫번째 문자 return 시간복잡도 : O(n) class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: ans = letters[0] for letter in letters: if letter > target: return letter return ans 시간복잡도 O(logn) class Solution: def nextGreatestLetter(self, letters: List[str], target: str) -> str: l, r = 0, len(letters) while l..

1351. Count Negative Numbers in a Sorted Matrix 문제는 매우 쉽다!! 코드 시간복잡도 : O(n * m) class Solution: def countNegatives(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) ans = 0 for r in range(m): for c in range(n): if grid[r][c] int: m = len(grid) ans = 0 for r in range(..

문제(18113. 그르다 김가놈) 김밥의 꼬다리를 제거한 김밥을 손질된 김밥 L이라 한다. 김밥은 양쪽 꼬다리를 균일한 Kcm만큼 잘라낸다. 만약 김밥의 길이가 2Kcm보다 짧으면 한쪽 꼬다리만 제거하고 김밥의 길이가 K보다 작거나 같으면 폐기한다. 손질된 김밥을 최대 Pcm로 최소M개를 만들려고 할 때, 최대 P를 찾아라. 만족하는 P가 없으면 -1을 출력 P는 양의 정수이다. 아이디어 문제를 잘 읽어야 풀 수 있다. 구현 난이도는 어렵지 않으나 문제의 내용이 애매하며 예제또한 애매하게 알려줘서 한번에 맞추기가 매우 어려운 문제이다. 내가 생각한 핵심아이디어는 김밥의 폐기조건을 정확하게 이해하고 구현해야한다. 김밥의 폐기조건 1. L = c * i: index = bisect.bisect_left(ar..

DSU(Disjoint Set Union) 교집합이 없는 두개의 집합(서로소)을 하나로 합치는 작업을 한다. 왜 필요한가? n이 10 ** 5 개인 그래프에서 단순 BFS나 DFS로 호출할 경우 모든 경로를 찾기 위해서는 n개인 10 ** 5번의 작업이 필요하다. 한 개를 찾을 경우 BFS나 DFS로 충분하지만 만약 e가 10 ** 5개를 찾아야 한다면 10 ** 10(10 ** 5 * 10 ** 5)번을 해야하며 시간초과가 나게 된다. 그렇기에 한번의 작업을 할때마다 parent를 업데이트해주는 DSU를 사용하면 해결할 수 있다. 시간복잡도 O(NlogN + ElogE + N + E) 구현 초기화 def __init__(self, n): self.parent = [i for i in range(n)]..

문제(23. Merge k Sorted Lists) linked list들이 들어있는 k배열이 있다. 그리고 각각의 linked list는 오름차순으로 정렬되어 있다. 배열 k에 있는 linked list들을 합쳐 오름차순으로 정렬한 linked list를 리턴하라. 문제에 대한 나의 생각 접근 하는 방법에 따라 이 문제의 난이도가 천차만별이라 생각한다. 만약 모든 linked list들을 한개씩 비교하는 방식으로 접근하면 처음 설계할 때 매우 중요하다고 생각한다. 그래서 이러한 방식은 다음에 시도하기로 하고 다른 방법으로 접근했다. 아이디어 linked list의 값을 저장할 새로운 배열을 생성한다. 그리고 linked list들의 값을 모두 새로 생성한 배열에 저장한다. 그리고 sort()를 사용하여..

아이고 이진탐색문제를 푸는데 bisect없이 풀어 보겠다고 도전했지만 보기 좋게 실패했다. 그래서 공부도 하고 라이브러리 의존도를 낮추기 위해 파이썬의 bisect의 bisect_left를 구현했다. 구조 bisect에는 대표적으로 bisect_left와 bisect_right가 있다. bisect_left와 bisect_right는 둘 다 배열에서 value가 들어갈 수 있는 적절한 위치를 반환하는 함수이다. 규칙 두 함수는 이진탐색을 할 때 이러한 규칙을 가진다. bisect_left : value arr[index] 예시 배열에 10 20 30 40 50 있다고 하자. 이 배열에서 25가 들어갈 위치를 찾을 때 배열 안에 같은 값이 없..

문제 제약사항 1

링크 문제 최소값과 최대값을 포함하는 서브어레이는 총 몇개인가? 제약사항 2

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 한개이다. 특정한 한개의 노드에서 나머지 노드의 최단 거리를 찾을 때 사용한다. 다익스트라 알고리즘의 원리는 이와 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3, 4를 반복한다. 즉, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 찾아 해당노드에서의 다른 노드의 거리를 비교해 갱신하는 것을 반복하는 것이 핵심이다. 그래서 이것을 빠르게 사용하기 위해서는 우선순위 큐를 사용하여 방문하지 않은 노드를 리스트에 삽입 후 사용하면 빠르게 접근할 수 있다. 구현 imp..

링크 문자열 s와 단어 사전인 wordDict가 있다. s는 wordDict안에 있는 단어들로 만들 수 있으면 True 없으면 False를 리턴하는 문제 제약사항 1