Medium174 [leetcode] 1048. Longest String Chain 문제 : https://leetcode.com/problems/longest-string-chain/ 먼저 words 배열을 문자열 길이 오름차순으로 정렬한다. 이제 반드시 [words[i], words[j]] (i < j) 식으로 string chain이 만들어진다. longest length를 저장하는 map을 하나 만든다. map dp; 위 map에는 key : words[i], value : longest length of a word chain 이 들어간다. 이제 words를 앞에서부터 탐색한다. 탐색 중인 words 문자열을 word2라고 했을 때 word2에서 문자를 하나씩 빼면서 string chain을 만드는 word1인지 확인한다. 만약 string chain을 만들 수 있는 word1.. 2019. 9. 11. [leetcode] 1155. Number of Dice Rolls With Target Sum 문제 : https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ DP 문제. int dp[d+1][target+1]; // dp[d][sum] = d개의 dice로 sum을 만들 수 있는 경우의 수 점화식은 위와 같다. 먼저 dp[1][1~target]을 1로 초기화 시킨다. (다이스 1개로 만들 수 있는 경우의 수 세팅) dp 배열을 행우선탐색으로 탐색하면서 배열을 채운다. (dice, sum) dp 요소를 채운다고 할 때, for(int face=1; face 2019. 9. 8. [leetcode] 904. Fruit into Baskets 문제 : https://leetcode.com/problems/fruit-into-baskets/description/ 슬라이딩 윈도우 문제. 인덱스를 가리키는 변수 l(왼쪽), r(오른쪽)을 둔다. tree[l]을 포함하여 수집할 수 있는 최대 범위를 r로 구한다. tree[l ~ r]이 과일종류가 3개 이상이 되기전까지 r을 증가시킨다. r을 구했으면 tree[l]을 포함할 때 수집할 수 있는 최대 과일 수를 구할 수 있다. (l~r 범위) ex) l = 0. r = 4 -> r - l + 1 = 5(0번째 인덱스를 포함하여 수집할 수 있는 최대 과일 수) 다음 탐색 시 tree 배열을 다시 탐색하지 않으려면 구한 범위에서 tree[l]이 아닌 과일의 종류가 무엇인지 알아야하고 이 과일이 가장 나중에.. 2019. 9. 3. [leetcode] 1162. As Far from Land as Possible 문제 : https://leetcode.com/problems/as-far-from-land-as-possible/ BFS로 풀었다. 먼저 grid를 모두 돌면서 land인 부분을 찾아서 queue에 x, y를 저장한다. queue가 빌 때 까지 돌면서 distance를 갱신한다. 탐색 시 x, y 위치에 현재까지 저장된 land와의 거리 + 1로 상하좌우 cell에 갱신가능한지 보아야 한다. 이 때 distance는 가장 가까운 land와의 거리이므로 거리가 아직 세팅되지 않은 경우(아직 어떠한 land와도 거리가 갱신되지 않음)와 거리가 세팅되었다면 이미 세팅된 거리보다 가까운 경우에만 갱신된다. 거리가 갱신된 경우 다시 queue에 현재 위치를 넣어준다. queue가 비었으면 cell의 거리 갱신이.. 2019. 8. 31. [leetcode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 문제 : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/ 링크드리스트 문제. 링크드리스트를 앞에서부터 탐색하면서 현재까지의 sum을 key, ListNode*을 value로 하는 map을 만들어서 저장해간다. 1, 3, 2, -3, -2, 5, 5, -5, 1 을 예로 들어보자. index 1 2 3 4 5 6 7 8 9 array 1 3 2 -3 -2 5 5 -5 1 subsum 1 4 6 3 1 6 11 6 7 합을 구하면 위 표와 같다. 링크드리스트라 인덱스로 표현되지는 않지만 말하기 쉽게 임의로 차례대로 인덱스를 붙여놓았다. 1. subsum으로 검색시 map에 없는 경우 인덱스 1~4가 이에 속한다.. 2019. 8. 28. [algospot][STRJOIN] 문자열 합치기 문제 : https://algospot.com/judge/problem/read/STRJOIN 그리디로 풀었다. 문자열의 길이가 가장 짧은 것 2개 부터 차례로 합쳐나간다. 최소 힙에 문자열들을 넣고 top에 있는 것 2개를 꺼내서 두 문자열의 길이의 합을 정답에 더해나간다. 최소 힙에 있는 문자열이 1개 남을 때까지 이를 반복한다. 최소 힙에서 특정 원소를 추가하는 작업은 O(logN)이므로 총 시간복잡도는 O(NlogN)이 된다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/STRJOIN.cpp fpdjsns/Algorithm 알고리즘 정리. Contribute to fpdjsns/Algorithm development by cr.. 2019. 7. 13. 이전 1 ··· 21 22 23 24 25 26 27 ··· 29 다음
