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,)교집합이 아닌 자리수부터 둘을 비교하여, 더 작은 숫자..

Problem : https://leetcode.com/problems/different-ways-to-add-parentheses Difficulty : Medium Status : Solved Time : 00:18:44  문제 설명  더보기주어진 문자열과 부호로 이루어진 수식을 입력으로 받아, 숫자와 연산자를 그룹화하는 모든 가능한 경우의 수를 계산하여 반환하라. 어떤 순서로 반환하여도 상관 없다. 생성된 테스트케이스는 출력값이 32비트 정수 내에 존재하며, 결과의 서로 다른 가짓수는 10^4를 초과하지 않는다. 풀이 처음에는 DP로 풀면서 뭐야, 왜 이렇게 복잡해? 싶었으나.. 내 착각이었다. DP로 풀면 결국 O(N^3)에 가까운 비효율적인 방식의 풀이가 되므로, 조금 다른 접근 방식이 필요하다..