LeetCode Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

보통 Tree 는 root 밑에 left와 right 가 있다. 포인터는 이 두개만 있는 것이 보통의 트리인데, 이 문제에서는 left와 right 를 root 를 통하지 않고 바로 next 로 연결하기를 원한다. root의 root 를 통해야 하는 right 에서 left로의 연결도 해야한다. Balanced Binary Tree 라면 쉽게 풀 수 있다. 또 그런 문제도 있었다. 이번문제는 unBalanced Binary Tree 이다.
Balanced 의 경우에는 root의 left의 left의 left 는 null이 나올 때 까지 계속 존재하고, 맨 왼쪽에 있는 TreeNode 에서 left 에서 right 로 직접이동할 수 있는 next 포인터를 추가해줬고, right의 오른쪽에 있는 left TreeNode 에 연결하기 위해서는 root 의 next 를 타고 넘어가 연결을 해줬다.

하지만, 이 문제는 맨 왼쪽의 TreeNode 가 없을 수도 있다. 보통의 방식으로 했다간, NullPointerException이 나올 수 있다. 어제 풀었던 Level-Order Traversal을 응용하기로 했다.
위에서 아래로 level 에 따라서 queue 에 들어가게 되고, 각 level 은 왼쪽에서 오른쪽으로 들어가게 된다. queue 에서 뽑아가면서 next pointer 를 만들어 주면 아무리 TreeNode 가 멀리 떨어져 있어도 포인터를 구축 할 수 있다. iteration으로 가장 가까운 형제노드를 찾는 것은 너무 어렵다.

LeetCode Happy Number

https://leetcode.com/problems/happy-number/
숫자의 각 자리 수를 제곱해서 합을 내고, 그것을 또 반복해서 마지막에 1이 나오는 수는 Happy Number 라고 정의를 했다.
이것은 숫자 n을 입력받았을 때, 그 수가 happy 한지 아닌지 판단해 내는 프로그램이다.
기본적인 idea는 간단하다. 각자리 숫자를 n%10 으로 해서 가져오고, 10으로 나눠 맨 뒷자리를 삭제하는 것이다. 두번째 while(n > 0) 은 놓치기 쉬운 edge 부분인데, 100 이라면 10으로 두번 나누면 1이 남고 마지막 것도 해줘야 하기 때문에 n이 0보다 클 동안은 계속 하는 것으로 했다.
이 연산을 할 때 1로 가지 못하고 영원히 연산이 끝나지 않는 경우는 언젠가 한번은 이전에 나왔던 중복된 수가 나오게 된다. 그렇기 때문에 HashSet 을 이용해서 삽입하면서 자동으로 판단할 수 있게 했다.

LeetCode Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/
tree traversal 에는 여러가지 방법이 있다. 제일 유명한 세가지.
preOrder, inOrder, postOrder 들이 제일 유명하다. 이번에는 tree 의 levelOrder 로 트리를 탐방하는 것이다. 위에서부터 차례대로 읽어가는 것이다.

이 문제는 queue 를 이용해서 풀 수 있더라.

queue 는 뒤로 들어와 앞으로 나가는 FIFO 방식이기 때문에, 맨 앞의 item 의 left와 right를 queue에 넣도록 한다. 그리고 맨 앞의 item 를 빼주면서 List에 추가해줌. queue 에서 item 을 뺄 때 몇개를 뺄 지는 loop 에 들어가기 전에 queue의 사이즈를 알아내도록 한다.

LeetCode Meeting Rooms

https://leetcode.com/problems/meeting-rooms/

이 문제는 좀 재밌었다.
미팅의 시작 시간과 종료시간이 적혀있는 interval 클래스 배열들을 입력 받아서 모든 미팅에 정시간에 제대로 참석할 수 있는지를 판단하는 것이다.
그러기 위해서는 다음 미팅의 start 가 전 미팅의 end 후여야 한다. 즉, 시간이 겹쳐서는 안된다는 것이다.
어떻게 풀어야 할 지 고민했었는데, 내가 생각했던 것은 모든 미팅 시간입력은 분(정수)로 입력이 되기 때문에, HashSet<Integer>를 이용하려고 했었다. start~end 매분을 HashSet 에 싹 다 입력을 하는 것이다. 그럼 다음 interval 의 입력이 있을 때, 혹시 시간이 겹치게 되면 HashSet 에서 false를 return 하는 것을 잡으려고 했는데, 이것은 O(n^2) 시간이 걸리게 된다. interval 배열과 end - start 입력.

푸는 방법으로는 sort를 이용하는 것이 있었다. Comparator 라는게 있어서 좀 재밌는 거 같다. PriorityQueue도 Comparator 를 이용해서 재배치가 가능하고, Arrays.sort 에도 Comparator를 붙일 수 있어서 자기의 기준에 맞춰서 배열을 정렬할 수 있게 되었다.
앞-- Object1, Object 2 ...... --뒤  return이 양수이면 순서를 바꾸고, 음수이면 그대로 둔다.
랜덤하게 입력받는 시간들을 start 시간으로 정렬해서 차례대로 입력을 받도록 한다. end 시간과 다음 미팅의 start 시간을 비교해서 판단을 하게 했다.

LeetCode Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/

이 문제는 String 을 입력 받아서 스페이스로 구분되어 있는 단어들을 역순으로 재배치 하는 것이다. 물론 단어내의 문자 순서는 그대로 유지하고

이것은 간단했다.
String 을 스페이스로 split 해서 역순으로 다시 붙이면 되는 것이다.
단, 살짝 까다로웠던 부분이 문장 마지막에 스페이스가 붙어 있으면 split 했을 때 배열에 들어가진 않지만, 문장 시작 부분에 스페이스가 붙어 있으면 첫배열에 들어간다는 것이다. 그것도 " " 가 아니라 ""로 들어가게 되어서 디버그 하기 전까지는 계속 오답처리가 되었었다. 그것 빼도는 쉽게 해결

LeetCode Reverse Words in a String 2

https://leetcode.com/problems/reverse-words-in-a-string-ii/

문장을 char 배열로 받아서 단어만 역순으로 재배치 하는 것이다.
해법은 금방 생각 났는데, 뭔가 좀 스마트한 방법은 없을까 고민을 좀 했었는데.. 솔루션을 봐도 특별한 건 없었다.

1. 전체를 뒤집는다. 0번과 n번, 1번과 n-1번 ......
2. 단어만 다시 뒤집는다. 0번과 i번, 1번과 i-1번 ...

완성. index 를 start와 end 두개를 써서 while로 start < end 일 동안 진행되게 했다.
for를 쓸경우, 0번부터 n번까지 돌리면 두번이 swap 되므로, 제자리로 돌아오게 되니. (n-1)/2 로 해서 중간까지만 한번씩 swap 되도록 한다.

LeetCode Binary Tree Upside Down

https://leetcode.com/problems/binary-tree-upside-down/

이 문제는 이해하기 좀 어려웠다. 어떤 규칙으로 되는지 찾는데 시간이 걸렸다.
문제 이름은 upside down 인데 그게 아니라 모든 노드를 시계방향으로 돌리는 것이다.
left 를 root 로 root 를 right 로, right 를 left로.
물론 left, right 에 있는 sub-tree 까지도 따라서 이동해야 한다.

이건 방법이 잘 안떠올라서 solution을 참고했다.
문제를 보고 바로 저런 해결책이 떠오른다면 대단할 것이다.
그리고 내가 본 solution 은 next, prev, cur 이런 변수를 이용해서 이해하기가 더 힘들었다.
그래서 new_left, new_right 를 이용해서 새로 짰고, 결과적으로는 같은게 나왔다.

마지막에 return new_right 를 하는 이유는 마지막으로 cur 이 들어가기 때문이고, node 가 하나밖에 없었다고 가정하면 그것은 right 로 이동을 한다.