Algorithm (2117) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 2559. Count Vowel Strings in Ranges https://leetcode.com/problems/count-vowel-strings-in-rangesprefix sum(누적합) 문제였습니다.📕 풀이방법📔 입력 및 초기화정답 배열 ans, 각 단어별 vowel str이 모음인지 여부를 저장할 배열 is_word_vowel을 선언 후 빈 배열로 초기화합니다.📔 풀이과정1. 각 단어의 처음과 끝이 모음인지 여부를 반환하는 함수 is_vowel_str을 선언 후 각 단어별로 호출해 결과를 is_word_vowel에 append해줍니다. 2. 누적합 vowel_str_sum을 선언 후 word의 길이만큼 순회하며 i번째 index까지의 vowel str개수를 구해 저장합니다. 3. queries정보를 순회하며 다음을 진행합니다. 3-1. 각 que.. (Python3) - LeetCode (Medium) : 1422. Maximum Score After Splitting a String https://leetcode.com/problems/maximum-score-after-splitting-a-string전수조사로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화점수 score를 선언 후 0으로 초기화합니다.📔 풀이과정1. 주어진 substring과 비교할 문자 mode를 입력받아 특정문자의 개수를 반환하는 getScore를 구현합니다. 2. s에 대해 1부터 len(s)-1까지 for loop를 수행하며 left, right로 부분 문자열을 만들고 각각 getScore한 결과의 최댓값을 score에 저장합니다.📔 정답 출력 | 반환score를 반환합니다.📕 Code📔 Python3class Solution: def maxScore(self, s: str) -> i.. (Python3) - LeetCode (Medium) : 2466. Count Ways To Build Good Strings https://leetcode.com/problems/count-ways-to-build-good-strings dp 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD를 선언 후 10**9 + 7로 초기화합니다.📔 풀이과정어떤 문자열 i길이를 만들기 위해 0을 zero개와 1을 one개를 사용할 때 다음과 같은 점화식을 세울 수 있습니다.$${D[i] = D[i-one] + D[i-zero]}$$ 1. 빈 문자열을 만드는 경우는 1이므로 dp[0]은 1로 초기화하고 1에서 high까지 for loop또는 재귀함수를 수행하며 각자 길이를 만드는 경우의 수를 구해줍니다. 2. low에서 high까지 다시 dp 값을 answer에 누적해 더해준 후 MOD연산을 적용해 갱신합니다.📔 정답 출력 | 반환a.. (Python3) - LeetCode (Hard) : 1639. Number of Ways to Form a Target String Given a Dictionary https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionarytop down dp로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화MOD, 한 단어의 길이 word_len, target의 길이 target_len, 각 단어의 열별 알파뱃의 빈도수를 저장할 해시맵인 freq_map, j번째 타겟의 문자를 만들기 위해 k번째 열의 word를 선택할 경우 만들 수 있는 문자들의 경우의 수를 의미하는 total_ways를 선언 후 적절히 초기화합니다.📔 풀이과정words의 길이가 모두 같기 때문에 단어들을 선택할 때 열별로 선택여부를 결정할 수 있습니다. words = ["abba", "baab", "abc.. (Python3) - LeetCode (Medium) : 1014. Best Sightseeing Pair.py https://leetcode.com/problems/best-sightseeing-pairheap또는 binary search를 사용해 풀어본 문제였습니다.📕 풀이방법📔 입력 및 초기화values의 길이를 length로 저장, 정렬된 값을 저장할 배열 sorted_values, 정답 변수 max_score를 선언 후 적절히 초기화합니다.📔 풀이과정values의 원소를 순회하며 다음을 진행합니다.values에서 values[i] + i값의 최댓값을 O(logN)만에 찾을 수 있다면 sorted_values의 마지막 원소 + values[j] - j값의 최댓값만 찾는다면 O(NlogN)만에 답을 찾을 수 있습니다. 다음 두 가지 방식을 생각해볼 수 있습니다. 1. sorted_values에 넣을 때.. (Python3) - LeetCode (Medium) : 494. Target Sum https://leetcode.com/problems/target-summemoization을 활용한 dfs문제였습니다.📕 풀이방법📔 입력 및 초기화1. 변수 depth선언 후 nums의 길이를 저장합니다. 2.(각 depth별 만들어진 숫자를 key로), 만드는 경우의 수를 value로 hash map인 memo를 선언 후 빈 객체로 초기화합니다.📔 풀이과정문제는 중복 상태를 메모이제이션으로 방지하며 재귀 호출을 최적화하는 방식으로 해결할 수 있습니다. nums 배열의 길이가 최대 20이며 각 원소는 1000 이하, 합계는 -20,000 ~ 20,000 범위를 가지므로 ${( n \cdot S = 20 \cdot 40,001 \approx 800,000 )}$번의 계산으로 해결 가능합니다.풀이 과.. (Python3) - LeetCode (Medium) : 515. Find Largest Value in Each Tree Row https://leetcode.com/problems/find-largest-value-in-each-tree-rowlevel별 탐색하는 BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 탐색을 진해할 deque변수 dq를 선언 후 root를 넣어줍니다. 2. level별 최댓값을 반환할 max_values를 선언 후 빈 배열로 초기화해줍니다.📔 풀이과정dq에 원소가 존재하는 동안 while loop를 수행하며 다음을 진행합니다.1. 현 dq의 size를 구해줍니다. 이는 즉 자식의 node 개수를 의미합니다. 2. 각 자식들이 가지는 원소들을 비교해 최댓값을 저장할 변수 max_value를 선언해줍니다. 3. size만큼 for loop를 수행하며 자식 노드들의 원소를 비교하며 dq에서 po.. (Python3) - LeetCode (Hard) : 3203. Find Minimum Diameter After Merging Two Trees https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees트리의 지름을 구하는 문제였습니다.📕 풀이방법📔 입력 및 초기화인접리스트 graph1, graph2를 구해줍니다.📔 풀이과정* 트리의 지름은 bfs를 두 번 수행해 구할 수 있습니다.* n개의 노드에 대해 n-1개의 간선이 보장되므로 노드번호 띄엄띄엄 포함된 간선이 입력으로 들어오는 경우가 없습니다.1. 첫 번째 bfs로 끝 노드를 구한 뒤 해당 노드를 시작점으로 두 번째 bfs를 수행한다면 트리의 지름이 나옵니다. 2. 해당 부분을 bfs_diameter라는 함수를 선언해 bfs를 두 번 수행한 결과로 구한 지름 diameter를 구하고 반환합니다. 3. 트리를 .. 이전 1 2 3 4 ··· 265 다음