greedy31 [Leetcode] 1768. Merge Strings Alternately 문제 : https://leetcode.com/problems/merge-strings-alternately/description/ 두 개의 문자열 word1과 word2가 주어집니다. 두 문자열을 번갈아가면서 시작 문자열이 word1이 되도록 문자를 추가하여 합칩니다. 만약 한 문자열이 다른 문자열보다 길다면, 추가 문자는 합쳐진 문자열의 끝에 붙입니다. 합쳐진 문자열을 반환합니다. word1, word2를 앞에서부터 탐색하면서 정답 문자열의 뒤에 추가해나갑니다. 만약 둘 중 하나의 문자열에 더 이상 추가한 문자가 없는 경우 문자가 없는 문자열은 무시합니다. 두 개의 문자열 모두 더 이상 추가할 문자가 없을때까지 이를 반복합니다. word1의 사이즈를 n, word2의 사이즈를 m이라 할 때, 시간복잡.. 2023. 4. 18. [Leetcode] 2300. Successful Pairs of Spells and Potions 문제 : https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/ spells와 potions이라는 길이가 각각 n과 m인 두 개의 양의 정수 배열이 주어집니다. 여기서 spells[i]는 i번째 주문의 강도를 나타내고, potions[j]는 j번째 물약의 강도를 나타냅니다. 그리고 주문과 물약의 강도를 곱한 값이 success 이상이면 성공적인 것으로 봅니다. 각 주문에 대해 성공적인 값을 이룰 수 있는 물약과 주문 pair 수를 나타내는 배열을 구하세요. 그리디 문제입니다. 먼저 spells와 potions를 정렬해야 하는데, 구하고자 하는 배열은 각 spell에 대한 값을 원하므로 spells는 해당 값의 인덱.. 2023. 4. 8. [Leetcode] 2405. Optimal Partition of String 문제 : https://leetcode.com/problems/optimal-partition-of-string/description/ 문자열 s가 주어졌을 때, 각 부분 문자열에 중복되는 문자가 없도록 하나 이상의 부분 문자열로 분할합니다. 즉, 각 문자는 분할된 부분 문자열 안에 최대 하나만 속해야 합니다. 각 분할에서 최소한의 부분 문자열 수를 반환합니다. 그리디로 풀 수 있습니다. 알파벳이 부분 문자열 안에서 등장했는지를 저장하는 배열을 하나 만듭니다. 문자열을 앞에서부터 탐색하면서 해당 배열을 갱신해나갑니다. 만약 탐색중인 문자가 이미 등장했다면 배열을 다시 false로 초기화 시키고 부분 문자열 수를 하나 증가시킵니다. 모든 문자열을 탐색했을 때 부분 문자열 수가 정답이 됩니다. 시간복잡도는 .. 2023. 4. 4. [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] 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. 이전 1 2 3 4 ··· 6 다음
