본문 바로가기

Medium166

[Leetcode] 623. Add One Row to Tree 문제 : https://leetcode.com/problems/add-one-row-to-tree/ 루트부터 자식으로 탐색해가면서 현재 depth가 새로운 노드가 추가되어야 하는 위치의 부모 노드라면 (1) (depth-1 이라면) 새로운 노드를 만들고 왼쪽 자식 노드에 들어갈 새로운 노드의 왼쪽 자식엔 원래의 왼쪽 자식 노드를 연결(2)한다. 오른쪽 자식 노드에 들어갈 새 노드의 오른쪽 자식엔 원래 오른쪽 자식 노드를 연결(3)한다. 새로 만든 노드들을 탐색 중인 노드의 자식 노드들로 연결(4)한다. 시간 복잡도는 O(N). N = 노트 수 소스코드 https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/623.%20Add%20One%20Ro.. 2022. 10. 5.
[Leetcode] 838. Push Dominoes 문제 : https://leetcode.com/problems/push-dominoes/description/ 배열을 하나 만들어서 문자열 길이만큼 0을 채운다. 이 배열에 L이라면 음수를, R이라면 양수를 채울 것이다. '.' 인 경우는 0. 'L', 'R'을 만나서 배열을 갱신할 때 시작점과 얼마나(인덱스) 떨어져 있는지 저장한다. 문자가 'L'이라면 왼쪽으로 가면서 -1, -2, -3 … 이런식으로 다음 문자를 만날 때까지 채워준다. 'R'이라면 오른쪽으로 가면서 1, 2, 3 … 을 다음 문자를 만날 때까지 채워준다. 문자가 있는 부분은 양수나 음수로 적절히 채운다. 나는 L은 '-1', R은 '1'을 채워줬다. 주의할 점이 2가지 있다. 1. "R . . . L" 이 경우 정답은 "R R . L.. 2022. 9. 28.
[Leetcode] 1680. Concatenation of Consecutive Binary Numbers 문제 : https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/ 숫자 n의 2진법 자리 수는 log2(n) + 1이다. 1부터 n까지 탐색하면서 이때까지의 합계를 sum이라 하자. 예를 들어, 숫자 5의 숫자 sum의 이진법 뒤에 추가한다고 하면 숫자 5의 이진법은 101. 자리수는 3이다. 따라서 sum을 앞으로 세 칸 움직이고 ( 2022. 9. 24.
[Leetcode] 1996. The Number of Weak Characters in the Game 문제 : https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/ 정렬 후, 그리디로 풀었다. 앞에서부터 탐색하면서 탐색중인 요소가 정답이 될 수 있는지 판단해야 한다. 공격, 방어 둘 다가 작아야 하므로. 먼저 공격을 내림차순으로 정렬한다. 공격은 내림차순 정렬했기 때문에 이때동안 탐색했던 모든 요소들의 공격은 현재 탐색하는 요소의 공격보다 크거나 같다(1). 따라서, 현재 탐색중인 방어보다 큰 값이 이때까지 탐색했던 방어들 값 중 있는지만 판단하면 된다. 큰 값을 구해야 하므로 탐색 중에 방어 값들 중 최대 값을 변수(maxDepen)에 저장해두고 이를 비교하면 O(1)만에 비교가능하다. 문제에서 공격, 방어를 비교할 때 str.. 2022. 9. 9.
[Leetcode] 792. Number of Matching Subsequences 문제 : https://leetcode.com/problems/number-of-matching-subsequences/ 문자열 s를 탐색하면서 특정 문자들의 인덱스들을 오름차순 배열에 저장해둔다. (charIndexes = 2차원 배열, charIndexes['a'] = 'a' 문자들의 등장인덱스 리스트) ex) s="abacb" => charIndexes['a'] = [0, 2], charIndexes['b'] = [1, 4], charIndexes['c']=[3] words 배열의 단어들의 문자를 앞에서부터 탐색하면서 탐색중인 문자가 문자열 s의 subsequences인지 확인해보자. words를 앞에서부터 탐색하면서 최근에 탐색한 s 인덱스를 index 배열에 저장해둔다. words[i] = c .. 2022. 7. 20.
[Leetcode] 1647. Minimum Deletions to Make Character Frequencies Unique 문제 : https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/ 문자열 s는 동일한 빈도를 가진 두 개의 다른 문자가 없으면 good이라 한다. 문자열 s 가 주어지면 s를 good 이라고 불리기 위해 삭제해야 하는 최소 문자 수를 구해라. 문자들의 빈도를 구한 뒤 배열에 저장해서 내림차순 정렬한다. "aaaabccccd" -> [4, 4, 1, 1] 배열을 탐색하면서 가능한 최대 빈도수를 구한 뒤 이와 비교하여 삭제해야 하는 문자 수를 구한다. 초기 최대 빈도 수는 배열의 첫번째 원소와 같다. 가능 최대 빈도수는 파란색의 경우 "가능 최대 빈도 수 - 1"로 갱신된다. 빨간 색의 경우 "탐색 중인 빈도 수.. 2022. 6. 28.