본문 바로가기
반응형

Medium130

[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.
[Leetcode] 1375. Bulb Switcher III 문제 : https://leetcode.com/problems/bulb-switcher-iii/ 1 ~ n 까지 번호가 매겨진 n개의 전구가 왼쪽에서 오른쪽으로 나열된 방이 있고, 전구번호를 가진 light 배열이 있다. 모든 전구들은 전구가 꺼져있다. k(0 ~ n-1) 번째에 light[k] 전구를 켠다. 만일 전구가 켜져 있고 해당 전구의 좌측에 있는 모든 전구들 또한 켜져 있다면 전구의 색들이 파란색으로 바뀐다. 켜진 전구들이 모두 파란색이 되는 순간의 횟수를 구해라. k번째에 켜진 모든 전구들이 파란색으로 변경되는 순간은 1 ~ k+1 번째의 전구가 모두 켜져있는 경우밖에 없다. 한 번엔 하나의 전구만 켜지고 전구의 번호는 겹치지 않으므로 이때동안 켜졌던 전구번호중 가장 큰 값이 k+1인 경우가.. 2021. 11. 24.
[Leetcode] 289. Game of Life 문제 : https://leetcode.com/problems/game-of-life/ m x n 2차원 배열이 있다. 배열은 1(live) 혹은 0(dead) 로 채워져 있다. 배열의 다음 상태는 각 셀의 8개의 이웃(수직, 수평, 대각선) 의 생사와 관련이 있다. 살아있는 상태의 셀의 살아있는 이웃 수가 2, 3개라면 다음에도 살아있을 수 있다. 하지만 이웃수가 너무적거나(0, 1) 너무 많으면(3초과) 인구과다로 죽게된다. 죽은 상태의 셀의 살아있는 이웃 수가 3개라면 번식한것처럼 되살아난다. 초기 생사 정보를 담은 배열이 입력으로 주어질 때 다음 상태를 반환하라. m x n 배열을 하나 만들어서 모든 셀을 탐색하며 각 셀의 살아있는 이웃들의 수를 저장한다. 다시한번 입력 배열을 탐색하며 만일 살아.. 2021. 11. 23.
반응형