본문 바로가기

알고리즘 문제/Leetcode283

[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]1431. Kids With the Greatest Number of Candies 문제 : https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/description/ 주어진 정수 배열 candies는 각각의 candies[i]가 i번째 아이가 가진 사탕 수를 나타냅니다. 또한, extraCandies라는 정수가 주어지는데, 이는 당신이 가진 추가 사탕 수를 나타냅니다. n명의 아이가 있을 때, i번째 아이에게 extraCandies를 모두 준 후, i번째 아이가 모든 아이 중에서 가장 많은 사탕을 가지게 될 경우, 그 결과를 true로 하는 n개의 원소를 갖는 boolean 배열 result를 반환하세요. 만약 그렇지 않은 경우 false로 합니다. 여러 아이들이 가장 많은 사탕을 가질수도 있습니다. candi.. 2023. 4. 17.
[Leetcode] 2218. Maximum Value of K Coins From Piles 문제 : https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/ 테이블 위에 n개의 동전 더미가 있습니다. 각 더미는 여러 가지 단위의 양의 동전으로 이루어져 있습니다. 한 번의 이동으로 단일 더미에서 맨 위의 동전을 선택하여 제거하고 지갑에 추가할 수 있습니다. piles는 각 더미를 나타내는 리스트이고, piles[i]는 i번째 더미의 위에서부터 아래쪽으로 순서대로 표시된 정수의 리스트입니다. k개의 동전을 정확히 선택하여 최적으로 지갑에 보관할 경우, 지갑에 가질 수 있는 동전의 최대 총 가치를 반환하세요. DP로 풀 수 있습니다. 먼저 dp에서 사용할 인덱스를 골라봅시다. 문제를 보았을 때 가장 먼저 골라볼 수 .. 2023. 4. 15.
[Leetcode] 516. Longest Palindromic Subsequence 문제 : https://leetcode.com/problems/longest-palindromic-subsequence/description/ 주어진 문자열 s에서 가장 긴 회문 부분 수열의 길이를 찾으세요. 부분 수열이란 다른 수열에서 일부 또는 전혀 없애지 않고 남은 원소들의 순서를 변경하지 않고 유도할 수 있는 수열입니다. DP로 풀 수 있습니다. dp[i][j] = s[i~j] 의 부분 수열의 가장 긴 펠린드롬 길이. dp[i][j] = dp[i+1][j-1] + 2 (s[i] == s[j]) = max(dp[i+1][j], dp[i][j-1]) (s[i] != s[j]) 점화식은 위와 같습니다. 만약, 문자열의 가장 앞과 뒤의 문자가 같다면 문자열의 가장 앞, 뒤 문자를 부분 수열에 포함하여 길.. 2023. 4. 14.
[Leetcode] 71. Simplify Path 문제 : https://leetcode.com/problems/simplify-path/description/ 주어진 문자열 path는 Unix 스타일 파일 시스템에서 파일 또는 디렉토리까지의 절대 경로(슬래시('/')로 시작)입니다. 이를 간소화된 카노니컬 경로로 변환하세요. Unix 스타일 파일 시스템에서 마침표(.)는 현재 디렉토리를 의미하며, 두 개의 마침표(..)는 상위 디렉토리를 의미합니다. 여러 개의 연속된 슬래시(//)는 하나의 슬래시(/)로 처리됩니다. 이 문제에서는 '...'와 같은 다른 마침표 형식은 파일, 디렉토리 이름으로 처리됩니다. 카노니컬 경로는 다음과 같은 형식을 가져야 합니다: 1. 경로는 슬래시(/)로 시작합니다. 2. 두 개의 디렉토리는 하나의 슬래시(/)로 구분됩니다... 2023. 4. 12.
[Leetcode] 2390. Removing Stars From a String 문제 : https://leetcode.com/problems/removing-stars-from-a-string/description/ 문자열 s가 주어지며, s는 별표(*)를 포함합니다. 한 번의 작업에서 다음을 할 수 있습니다: s에서 별표 하나를 선택합니다. 그 별표 왼쪽에서 가장 가까운 비 별표 문자를 제거하고, 그 별표 자체도 제거합니다. 모든 별표가 제거된 후의 문자열을 반환합니다. 참고 - 입력은 항상 작업이 가능하도록 생성됩니다. - 결과 문자열은 항상 고유함이 보장됩니다. stack을 사용합니다. 문자를 앞에서부터 탐색하면서 별표가 아닌 문자인 경우 스택에 문자를 넣습니다. 별표인 경우 스택의 탑에 있는 문자를 제거합니다. 모든 문자열을 탐색했으면 스택에서 문자를 제거하면서 정답 문자열.. 2023. 4. 11.