Problem : https://leetcode.com/problems/minimum-string-length-after-removing-substrings Difficulty : Easy Status : Solved Time : 00:03:54  문제 설명  더보기대문자 알파뱃으로만 이루어진 문자열 s를 입력으로 받는다. 이 문자열에 어떤 동작을 시행할 수 있는데, 한 동작에서 s 내의 "AB" 혹은 "CD"로 등장하는 부분문자열을 지울 수 있다. 이 동작으로 얻을 수 있는 가능한 가장 작은 문자열의 길이를 구하여라. 부분문자열을 지운 후에 새로운 "AB" 혹은 "CD" 문자열이 생성될 수 있음을 명심하라. 풀이 그리디하게, 스택을 사용하면 쉽게 풀 수 있다.스택에 문자열의 문자들을 저장하되, 현재 문..

Problem : https://leetcode.com/problems/make-sum-divisible-by-p Difficulty : Medium Status : Solved Time : 00:39:33  문제 설명  더보기양의 정수로 구성된 배열 nums가 주어졌을때, 남은 원소의 합이 p로 나누어지는 가장 작은 부분배열(길이가 0일 수도 있다)을 제거하도록 한다. 전체 배열을 제거하는 것은 허락되지 않는다. 그 가장 작은 부분배열의 길이를 반환하라. 만약 불가능하다면 -1을 반환하라. 부분배열은 배열의 연속된 원소로 이루어진 구간을 의미한다.  풀이 부분합으로 풀어야하나... DP로 풀어야하나... 꽤 고민하다가 DP를 선택했고, 가차없이 틀렸다. 부분합으로 풀이해보도록 하자. 우리는 조금 다른 ..

Problem : https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix Difficulty : Hard Status : Solved Time : 00:16:41  문제 설명더보기비어있지 않은 문자열로 구성된 n 크기의 words 배열을 입력으로 받는다.우리는 word 문자열에 대한 점수를 word 문자가 words[i]의 접두사를 만족하는 words[i]의 개수로 정의한다. * 예를 들어, words = ["a", "ab", "abc", "cab"]라면 "ab"의 점수는 2이다. "ab"는 "ab"와 "abc"의 접두사이기 때문이다. 크기가 n인 answer 배열을 반환하라. 이 때 answer[i]는 words[i]의 모든..

Problem : https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix Difficulty : Medium Status : Solved Time : 00:18:42  문제 설명  더보기양의 정수로 구성된 arr1, arr2가 주어진다. 양의 정수의 접두사는 제일 왼쪽부터 시작하는 하나 이상의 숫자로 구성된 정수를 의미한다. 예를 들어, 12345에서 123은 접두사이지만 234는 접두사가 아니다. a, b의 공통 접두사가 c라면, c는 a와 b 양 쪽 모두 접두사이다. 예를 들어서, 5655359와 53554는 공통 접두사로 565를 가지지만 1223과 43456은 공통 접두사를 가지지 않는다. arr1에 속하는 정수 x와,..

Problem : https://leetcode.com/problems/extra-characters-in-a-string Difficulty : Medium Status : Solved Time : 00:22:04  문제 설명  더보기0-인덱스의 문자열 s와 단어들의 사전인 dictionary가 주어진다. s를 하나 이상의 겹치지 않는 부분 문자열로 나누며, 부분 문자열은 dictionary 내에 존재해야 한다. 이 부분 문자열 어디에도 속하지 않는 잉여 문자들이 존재할 수 있다. s를 최적으로 쪼갠다고 가정할 때, 남는 잉여 문자들의 최소 개수를 반환하라. 풀이 순수 DP로도 풀 수 있다. 조금 비효율적이겠지만.현재 idx를 기준으로현재 idx의 문자가 잉여 문자임을 가정한다. 그렇다면 dp[idx+..

Problem : https://leetcode.com/problems/lexicographical-numbers Difficulty : Medium Status : Solved Time : 00:14:11  문제 설명  더보기정수 n을 입력으로 받았을 때, [1, n] 범위의 정수를 사전식 순서대로 정렬하여 반환하라. 이 때, O(n)시간복잡도와 O(1) 추가 공간복잡도 알고리즘을 사용해야만 한다. 풀이 사전식 순서 = DFS. 사전식 순서의 규칙을 떠올려보자.한 숫자가 다른 숫자의 진부분집합이면, 그 숫자가 앞에 와야 한다 (예 : 111 -> 1111 -> 1112)그렇지 않다면..처음 자리부터 두 숫자의 교집합을 구하고 (예 : 111452,)교집합이 아닌 자리수부터 둘을 비교하여, 더 작은 숫자..