Medium174 [Leetcode] 147. Insertion Sort List 문제 : https://leetcode.com/problems/insertion-sort-list/ 단일 linked list의 헤드가 주어질 때 삽입 정렬을 이용하여 이들을 정렬한뒤 정렬된 linked list의 헤드를 반환하라. 정렬된 링크드 리스트의 헤드를 저장하기 위해 ListNode를 하나 만들고 이 노드의 주소값을 newHead 변수에 저장한다. 원본 head의 노드를 처음부터 하나씩 정렬시켜야 하므로 앞에있는 노드부터 하나씩 탐색하며 newHead를 헤드로 하는 링크드 리스트의 적절한 위치에 연결해준다. 탐색하는 노드의 포인트를 originNode라 하자. 정렬된 링크드 리스트의 적절한 위치를 찾을 때 노드를 적절한 위치에 넣기 위해서는 해당 노드의 앞에 위치하는 노드를 알아야 한다. 예를 .. 2021. 12. 15. [Leetcode] 1306. Jump Game III 문제 : https://leetcode.com/problems/jump-game-iii/ 음이 아닌 정수 arr 배열과 시작 인덱스 start가 주어진다. 인덱스 i에 있을 때 i+arr[i], i-arr[i] 인덱스로 점프할 수 있다고 할 때 값이 0인 인덱스에 도달할 수 있는지를 구하라. i번째 인덱스를 방문한 적이 있는지를 저장하는 배열을 하나 만들고 시작 인덱스 start부터 i+arr[i], i-arr[i] 인덱스 위치로 탐색하며 이미 방문한 적이 있다면 더 이상 탐색하지 않고 탐색한적이 없으면 방문여부를 true로 갱신한 다음 해당 값이 0이면 true를 반환한다. 해당 값이 0이 아닌 경우 i+arr[i], i-arr[i]가 배열 arr 범위 내부이며 방문한 적 없는 인덱스인 경우 탐색을 이.. 2021. 12. 9. [Leetcode] 337. House Robber III 문제 : https://leetcode.com/problems/house-robber-iii/ 이진 트리로 구성된 집들의 구조가 있다. 도둑은 집들에 침입해 도둑질을 하려고 하는데 연결된 집을 동시에 털면 경찰에 연락이 간다. 경찰에 연락이 가지 않게 집들을 도둑질하려고 할 때, 훔칠수 있는 최대 금액을 구해라. memoization을 위해 TreeNode*을 키 값으로 하고 해당 노드를 헤드노드로 한 서브트리에서 조건을 만족하며 훔칠 수 있는 최대 금액을 저장한다. 탐색 중인 노드를 훔쳤다면 왼쪽, 오른쪽 자식 노드들은 훔치면 안되므로 왼쪽 자식 노드의 자식 노드들, 오른쪽 자식 노드의 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합이 정답이 될 수 있다. 또한 탐색 중인 노드를 .. 2021. 12. 5. [Leetcode] 82. Remove Duplicates from Sorted List II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ 정렬된 linked list의 head 노드가 주어지면 중복된 번호를 가진 노드들은 모두 삭제하고 고유한 번호를 가진 노드들만 남겨라. head 노드의 앞에서부터 탐색하며 탐색중인 노드의 next 노드가 없거나 탐색중인 노드의 val 와 next 노드의 val이 다른경우 고유한 노드가 된다. 이 경우 탐색중인 노드는 삭제하지 않고 남겨야 하므로 별도의 ListNode 포인터 변수(let, prev)에 저장해둔다. prev->next에 현재 노드를 연결시켜준 뒤 prev도 탐색중인 노드로 갱신한다. 그리고 최초로 찾은 고유한 노드는 새로운 head 노드가 되므로 이를 또 다른.. 2021. 12. 3. [Leetcode] 61. Rotate List 문제 : https://leetcode.com/problems/rotate-list/ linked-list 의 head 노드가 주어지면 오른쪽으로 k만큼 회전한 뒤의 linked-list의 head를 반환하라. 입력으로 주어진 링크드 리스트를 한 번 탐색하면서 전체 길이를 구한다. (let, cnt) 만약 오른쪽으로 cnt번 회전하면 원래의 링크드 리스트와 동일해지므로, 나머지 연산을 한 k % cnt 만큼만 오른쪽 회전시키면 된다. 링크드 리스트를 다시 한 번 탐색하면서 o -> o -> o -> o -> o 만일 위와 같은 링크드 리스트가 있고 k가 2라면 빨간색 노드가 새로운 헤드 노드가 될 것이다. 즉, head노드의 cnt - k번째 next 노드가 헤드노드가 된다. 회전한 뒤의 모습은 원래 링.. 2021. 12. 2. [Leetcode] 721. Accounts Merge 문제 : https://leetcode.com/problems/accounts-merge/ accounts 2차원 배열이 주어질 때, accounts[i]의 첫번째 요소가 이름이고 나머지는 이메일이다. 두 계정에 공통 이메일이 있는 경우 두 계정을 합쳐라. Union Find 로 풀었다. email을 키 값으로 최근에 email을 가진 유저 이름의 인덱스를 저장한다. 만일 탐색중인 이메일에 이미 인덱스가 저장되어 있다면 union 함수로 현재 탐색하는 account 인덱스와 이메일의 최근 인덱스를 합친다. 동일한 이메일을 가지는 account 인덱스끼리 다 합쳤다면 이후엔 동일 부모를 가지는 account들을 합쳐서 정답 배열을 만들어낸다. 시간복잡도는 O(NM). N = |accounts|, M = |.. 2021. 11. 29. 이전 1 ··· 5 6 7 8 9 10 11 ··· 29 다음