알고리즘 문제408 [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. [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. [algospot][LUNCHBOX] Microwaving Lunch Boxes 문제 : https://algospot.com/judge/problem/read/LUNCHBOX 그리디하면 나오는 단골 문제. 전자레인지에 돌리는 행동은 선형적이지만 먹는 것은 병렬적으로 처리할 수 있다. 따라서 시간을 효율적으로 사용하려면 중요한 건 먹는 시간이다. 병렬적으로 처리된다고 했을 때 가장 먼저 시작되어야 하는 것은 시간이 가장 오래 걸리는 것이다. 따라서 도시락을 먹는 시간의 내림차순으로 정렬하고 이 때 모든 도시락을 데우고 먹는 데 걸리는 시간(1)을 구하면 이 결과가 정답이 된다. (1)을 구하는 방법은 도시락을 정렬한 뒤 앞에서부터 탐색하면서 데우는 시간과 먹는 시간을 누적해간다. 데우는 시간은 선형적이므로 각 도시락의 데우는 시간의 합이다. 누적된 먹는 시간은 도시락을 데울 때 그 .. 2019. 7. 13. 이전 1 ··· 51 52 53 54 55 56 57 ··· 68 다음
