알고리즘 문제408 [Leetcode] 1402. Reducing Dishes 문제 : https://leetcode.com/problems/reducing-dishes/description/ n개의 요리의 만족도가 있고 어떤 요리든 1단위 시간 안에 조리할 수 있습니다. 한 요리의 "Like-time coefficient"은 "해당 요리와 이전 요리를 모두 조리하는데 걸리는 시간 x 해당 요리의 만족도"(time[i] * satisfaction[i]) 입니다. 요리는 어떤 순서로든 준비할 수 있고, 일부 요리를 버릴 수도 있습니다. 가능한 Like-time coefficient의 최대값은 얼마입니까. 만족도는 음수가 가능합니다. time[i]는 양수이기 때문에 모든 음수 만족도를 제거하는게 최대값을 만드는 것이라 생각될 수 있지만, 다음과 같은 경우는 다릅니다. satisfact.. 2023. 3. 29. [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. 이전 1 2 3 4 5 6 ··· 68 다음
