본문 바로가기

알고리즘 문제395

[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] Weekly Contest 312 contest : https://leetcode.com/contest/weekly-contest-312/ 1. Sort the People (Easy, 3) 문제 : https://leetcode.com/contest/weekly-contest-312/problems/sort-the-people/ heights 배열로 {heights[index], index}를 요소를 가지는 배열을 만든 뒤 높이내림차순 정렬. 정렬된 배열을 앞에서부터 탐색하면서 names[index]를 정답에 차례대로 세팅 시간복잡도는 O(NlogN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/2418.%20Sort%20the%20People.cpp 2... 2022. 9. 25.
[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] 936. Stamping The Sequence 문제 : https://leetcode.com/problems/stamping-the-sequence/ 이전에 찍힌 스탬프는 덮히고 가장 마지막에 찍히는 스탬프가 최종 글자가 된다. 따라서 뒤에 찍힐수록 중요하게 봐야하는 값이 되므로 스탬프가 찍히는 역순으로 생각한다. 예를 들어 stamp="abc", target="ababc"라면 2번째 자리에 "abxxx" 로 x자리가 스탬프가 찍히고 스탬프가 찍힌 x 자리는 어느 문자가 오든 관계없는 자리가 된다. 따라서 0번째에 스탬프를 찍는다. 그럼 [2, 0]으로 도장이 찍히는데 역순으로 생각한 것이기 땜문에 [0, 2]가 정답이 된다. [0, 2] 로 도장을 찍은 경우 _ _ _ _ _ -> a b c _ _ -> a b a b c 가 된다. 따라서 targ.. 2022. 8. 21.