리트코드 75 11일 차, Hash Map, Linked List, DFS 패턴 문제를 하나씩 풀어봤다.
1207. Unique Number of Occurrences
주어진 배열 arr에 대해서 각 값이 출현한 횟수가 unique 하다면 true, 그렇지 않으면 false를 리턴한다.
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.
각 문자가 출현한 횟수를 해시맵에 저장한 다음(freqMap), 출현한 횟수로 Set을 만들어서(freqSet) 둘의 크기가 같은지 확인한다. 만약 출현한 횟수가 unique 하다면 freqMap의 크기와 동일할 것이다.
class Solution {
public boolean uniqueOccurrences(int[] arr) {
Map<Integer, Integer> freqMap = new HashMap<>();
for(int value : arr) {
int freq = freqMap.getOrDefault(value, 0);
freqMap.put(value, freq+1);
}
Set<Integer> freqSet = new HashSet<>(freqMap.values());
return freqMap.size() == freqSet.size();
}
}freqMap에 배열의 값을 모두 넣는 데에 드는 시간이 O(n), freqMap의 값들을 다시 freqSet에 넣어서 초기화 할 때 O(n)이 걸려서 시간 복잡도는 O(n), 공간 복잡도는 freqMap, freqSet을 저장하는데 O(n) 걸려서 마찬가지로 O(n)이다.
206. Reverse Linked List
주어진 linked list를 뒤집고(reverse), 뒤집은 linked list의 head를 리턴한다.
Given the head of a singly linked list, reverse the list, and return the reversed list.
포인터를 적절히 사용하면 상수 공간복잡도로 문제를 풀 수 있다. 말로 설명하기 힘든데, 코드에 따라 변수에 저장된 노드가 어떻게 변하는지 확인해 보면 어떻게 동작하는지 알 수 있을 것이다. prev가 주어진 원래 linked list의 tail node가 들어가서 prev를 리턴한다.
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev=null, cur=head;
while(cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}시간 복잡도 O(n), 공간 복잡도 O(n).
872. Leaf-Similar Trees
이진 트리의 모든 leaft node들을 왼쪽에서부터 오른쪽 순서로 나열한 배열이 있을 때 두 배열 roo1, root2의 leaf value 배열이 같으면 leaf-similar 하다고 부른다. root1, root2 노드가 leaf-similar 했는지 아닌지 반환하는 함수를 구현하라.
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
leafSimilar 메소드는 먼저 leaf value sequence를 구현하는 메서드를 구현하고, 두 sequence를 비교하면 된다. leafSequence는 재귀적으로 노드를 순회하면서 leaf node이면 리스트에 추가하는 방식으로 재귀적으로 구현할 수 있다. 그다음은 두 배열의 값을 비교하는 것이라 간단히 구현할 수 있다.
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> seq1 = new ArrayList<>();
List<Integer> seq2 = new ArrayList<>();
getLeafSequence(root1, seq1);
getLeafSequence(root2, seq2);
return seq1.equals(seq2);
}
private void getLeafSequence(TreeNode root, List<Integer> seq) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
seq.add(root.val);
}
if (root.left != null) {
getLeafSequence(root.left, seq);
}
if (root.right != null) {
getLeafSequence(root.right, seq);
}
}
}트리 root1, root2의 노드 개수를 각각 m, n이라고 했을 때 leaf value sequence를 만드는 시간 복잡도는 O(m), O(n)이다. 이진 함수의 리프 노드 개수는 최대 logm, logn이고, leaf sequence의 값을 전부 비교해야하기 때문에 O(min(logm, logn))이 될 것이다. 그런데 Big O notation에서는 가장 큰 factor만 표시하기 때문에 시간 복잡도는 O(m+n)이 된다.
