분류 전체보기 (2341) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 2381. Shifting Letters II https://leetcode.com/problems/shifting-letters-iidifference array를 사용해본 문제였습니다.📕 풀이방법📔 입력 및 초기화s의 길이 length, 변화량을 저장할 배열 diff, 변화량의 누적값 배열 diff_sums를 선언 후 적절히 초기화합니다.📔 풀이과정단순히 매 shift연산에 대해 for loop를 수행하며 문자를 바꾸게 되면 5만*2로 시간초과를 받게 됩니다. 따라서 O(n)의 연산을 적용하기 위해 변화량을 기록해 누적합을 사용해야 됩니다.1. shifts를 순회하며 현재 shift에 대해 시작 인덱스와 끝 인덱스를 방향에 따라 전처리 해줍니다. 시작인덱스 ~ 끝 인덱스까지 해당 방향이 기록되므로 끝 인덱스 + 1부터는 누적량을 고려해 .. (Python3) - LeetCode (Medium) : 1930. Unique Length-3 Palindromic Subsequences https://leetcode.com/problems/unique-length-3-palindromic-subsequences아이디어로 해결해야하는 문자열 문제였습니다.📕 풀이방법📔 입력 및 초기화1. s에 사용된 고유한 알파뱃들을 저장할 set letters를 선언후 s에 사용된 고유 문자들을 저장합니다. 2. 정답변수 ans를 선언 후 0으로 초기화합니다.📔 풀이과정다음 palindrome은 모두 'ata'라는 문자열 한개에 대한 부분 문자열입니다.a__t__aa_ta____a__t_apalindrome은 어떻게 만들어질까요? 고유한 문자의 왼쪽과 오른쪽 index를 찾고 그 사이 아무문자를 사용해 길이 총 3개의 문자열을 만든다면 palindrome이 됩니다. palindrome을 찾기 위해.. (Python3) - LeetCode (Medium) : 2270. Number of Ways to Split Array https://leetcode.com/problems/number-of-ways-to-split-arrayprefix sum 문제였습니다.📕 풀이방법📔 입력 및 초기화1. length 선언 후 nums의 길이를 저장합니다.2. 누적합을 저장할 배열 sums를 선언 후 length만큼 0으로 초기화합니다. 3. valid_splits를 선언 후 0으로 초기화합니다. 4. sums의 누적합을 구해 갱신해줍니다.📔 풀이과정0에서 length - 2까지 for loop를 수행하며 split된 left_sum, right_sum을 구해줍니다. 0부터 i까지의 합이 sum[i], i+1부터 끝까지의 누적합은 sum[length-1] - sum[i]가 되므로 O(n)만에 valid 한 splits인지 구할 수 .. (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에 넣을 때.. 이전 1 2 3 4 5 6 ··· 293 다음 목록 더보기