❒ Description제목게임 맵 최단거리링크https://school.programmers.co.kr/learn/courses/30/lessons/1844자료구조/알고리즘Map, Queue / 넓이 우선 탐색(BFS)시간 복잡도 O(row수 * col수)  BFS를 사용해서 해결 할 수 있는 문제이다. 문제의 핵심 포인트는 maps[row][col] 값을 업데이트 해주는 부분이다.시간 복잡도의 경우는 모든 노드를 한 번씩 방문하기 때문에 O(N*M)의 시간 복잡도를 갖는다.     ❒ Solution더보기import java.util.LinkedList;import java.util.Queue;class Solution { private final int[][] dirs = {{-1, 0}, {..

❒ Description제목Cheapest Flights Within K Stops링크https://leetcode.com/problems/cheapest-flights-within-k-stops/description/자료구조비선형 (그래프) - 최단거리시간 복잡도O(ElogV)다익스트라 알고리즘을 사용해서 풀 수 있는 문제이며, Comparable 인터페이스도 활용할 수 있다.이 문제는 경유 횟수가 제한되어 있어서 굉장히 까다로웠다.     ❒ Solution1.  단순 solvepublic int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { //1. filghts 배열을 통해 graph 생성 List> graph..

❒ Description제목Course Schedule링크https://leetcode.com/problems/course-schedule/description/자료구조비선형 (그래프)시간복잡도위상정렬 : O(v+e) 이번 문제는 재귀로도 풀수 있지만, Topological Sorting 알고리즘을 사용해서도 풀수 있는 문제다.   ❒ Solution1. 재귀 구조public boolean canFinish(int numCourses, int[][] prerequisites) { Map> finishToTakeMap = new HashMap(); for (int[] prerequisite : prerequisites) { finishToTakeMap.putIfAbsent(prere..

❒ Description제목Permutation링크https://leetcode.com/problems/permutations/description/자료구조비선형 (그래프)시간복잡도 O(n!)Permutation(순열)이란, 모든 가능한 경우를 그래프 형태로 나열한 결과라고 할 수 있다.이 문제는 BackTraking을 통해서 해결하는 문제인데, 모든 가능한 순열을 생성하기 때문에nums의 크기가 커질수록 시간이 급격히 증가한다. ❒ Solution1. Solution1public class Solution { public List> permute(int[] nums) { List> results = new ArrayList(); List elements = Arrays.s..

❒ Description제목완주하지 못한 선수링크https://school.programmers.co.kr/learn/courses/30/lessons/42576자료구조선형 (해시)시간복잡도O(n + k)이번 문제는 해시맵을 사용하여 간단하게 해결 할 수 있는 문제인데 다른 풀이에서 HashMap을 생성할 때 Stream을 이용한 풀이가 있어서 메모.   ❒ Map 생성Code 1다음과 같은 배열 `"A", "B", "C", "A", "C", "A"`에서 각 요소가 몇 번 나왔는지를 Map 자료구조로 표현할 때나는 주로 아래와 같이 코드를 작성했다.Map counter = new HashMap();for (String name : students) { counter.put(name, counter.get..

❒ Description제목K Closest Points to Origin링크https://leetcode.com/problems/k-closest-points-to-origin/description/자료구조선형 (우선순위 큐)시간복잡도O(nlogn) 이번 문제는 우선순위 큐를 사용하여 해결하는 문제이다. Sort, Heap, Quick Select를 사용하는구현도 있는데 이것에 대해서는 해당 섹션 공부할 때 같이 볼 예정이다. 이 문제는 Comparator와 Comparable 중 하나를 사용해서 우선순위를 결정해줘야 한다.Comparator를 통해서 우선순위를 정해줄 경우 main method에서 `Comparator#compare`메서드를제정의 해줘야해서 DDD에 어긋난다. 반면에 Comparabl..

❒ Description제목Merge K sorted Lists링크https://leetcode.com/problems/merge-k-sorted-lists/description/자료구조선형 (우선순위 큐)시간복잡도O(nlogk) 이번 문제에서도 가상의 노드 Root를 사용되었다. 이쯤 느껴지는 것은 뭔가 정렬이 들어가는경우에는 가상의 노드 접근을 생각해보는 것도 좋은 거 같다. 아무튼 문제의 핵심은 자료구조 Priority Queue를 사용해서 해결하는 문제였다.Priory Queue에 대한 정리는 이곳에 할 것이다.    ❒ Solution전체 코드더보기public ListNode mergeKLists(ListNode[] lists) { PriorityQueue pq = new PriorityQ..

❒ Description제목Design Circular Deque링크https://leetcode.com/problems/design-circular-deque/description/자료구조선형 (배열 / 이중 연결 리스트)시간복잡도O(1)이번 문제는 이중 연결 리스트로 Circular-Deque를 구현하는 문제였다.근데 사실 이중 연결 리스트로  Circular-Deque를 구현하면 원형의 이점을 살릴 수 없다.실제로 원형의 이점을 살리기 위해선 이 문제를 연결리스트가 아닌 배열로 풀이해야 한다.따라서 이번 문제는 이중 연결 리스트와 배열 모두 구현 해볼 것이다.   ❒ Solution1. 이중 연결 리스트 (Doubly-Linked List)더보기public class MyCircularDeque {..