알고리즘 문제/Leetcode283 [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] 1160. Find Words That Can Be Formed by Characters 문제 : https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/ Map을 이용. 일단 chars 문자열을 모두 방문하면서 { 문자, 개수 }를 map에 저장한다. words 문자열들을 방문하면서 현재 탐색 중인 문자열의 문자도 탐색한다. 탐색 중인 문자가 chars map에 있는지 확인하고 있는 경우 개수를 1개 빼준다. 만약 문자가 map에 없거나 map에 탐색중인 문자의 개수가 0개라면 good string이 아니므로 탐색을 종료한다. good string이 될 수 있는 경우(탐색중인 문자열의 모든 문자들을 탐색완료 시) 문자열의 문자 길이를 정답에 더해준다. N : strings의 개수 / M : strings[i]의 길.. 2019. 9. 1. [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] 1172. Dinner Plate Stacks 문제 : https://leetcode.com/problems/dinner-plate-stacks/ let) capacity = 2 index 0 1 2 3 stack 4 1 3 5 fullStack : 가득찬 스택 인덱스 (2) blankFullStack : fullStack 사이사이의 index (0, 1, 3(3인덱스 스택이 가득찼다가 삭제된 경우)) stackMap : key - index, value - stack ({0, {1}}, {2, {4,3}}, {3, {5}) push 처음 push하는 경우는 0번 인덱스 stack에 push. 가득찬 스택들 중간에 빈 곳이 있는 경우(blankFullStack이 있는 경우) 빈 곳 중 가장 왼쪽에 넣어준다. 왼쪽부터 차례대로 스택들이 모두 차있는 경.. 2019. 8. 30. [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. 이전 1 ··· 36 37 38 39 40 41 42 ··· 48 다음
