Cracking the coding interview라는 아주 유명한 코딩 면접 준비용 책이 있는데 아직 완독한 적이 없다. 요즘 리트코드같은 플랫폼이 워낙 잘 구현되어 있으니 코드 짤 때 메서드 자동 완성을 해주기도 하고 테스트 케이스를 짜면 돌려주고 채점까지 해주니 굳이 손으로 코딩하는 연습과는 멀어지게 되는 것 같다. 오늘도 연습해 보는데 코테는 감을 유지하는 게 중요한 것 같다.
2215. Find the Difference of Two Arrays
answer[0]은 nums1 - nums2 차집합 리스트, answer[1]은 nums2 - nums1 차집합 리스트를 반환해야 한다. 리스트 내 숫자의 순서는 상관없다. 또한 리스트는 distinct 한 숫자 리스트기 때문에 중복이 없어야 한다.
Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0] is a list of all distinct integers in nums1 which are not present in nums2. answer[1] is a list of all distinct integers in nums2 which are not present in nums1.
Note that the integers in the lists may be returned in any order.
중복이 없어야 하니까 Set을 사용한다. nums1, nums2를 각각 HashSet에 넣고 반복문을 돌면서 공통인 숫자를 제거한다.
class Solution {
public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
Set<Integer> distinct1 = new HashSet<>();
Set<Integer> distinct2 = new HashSet<>();
for(int n : nums1) {
distinct1.add(n);
}
for(int n : nums2) {
distinct2.add(n);
}
for (int n : nums2) {
if (distinct1.contains(n)) {
distinct1.remove(n);
}
}
for (int n : nums1) {
if (distinct2.contains(n)) {
distinct2.remove(n);
}
}
List<List<Integer>> ret = new ArrayList<>();
ret.add(new ArrayList(distinct1));
ret.add(new ArrayList(distinct2));
return ret;
}
}너무나 직관적인 문제여서 복잡도 계산이 딱히 필요 없는 듯... 시간 복잡도 O(m+n), 공간 복잡도 O(m+n)
2390. Removing Stars From a String
주어진 문자열에서 별(*)을 없애는데 별 왼편 가장 가까운 별이 아닌 문자를 함께 지운다. 입력 문자열은 항상 처리가 가능한 것만 들어온다. 그리고 결과는 항상 유일하다.
You are given a string s, which contains stars *.
In one operation, you can:
Choose a star in s.Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note: The input will be generated such that the operation is always possible.It can be shown that the resulting string will always be unique.
StringBuilder를 사용하여 문자를 하나씩 넣다가 별 문자를 만나면 가장 마지막에 넣은 문자를 제거한다. 역시 직관적인 문제다.
class Solution {
public String removeStars(String s) {
int len = s.length();
StringBuilder sb = new StringBuilder();
for(int i=0; i<len; i++) {
if (s.charAt(i) != '*') {
sb.append(s.charAt(i));
} else {
sb.deleteCharAt(sb.length()-1);
continue;
}
}
return sb.toString();
}
}시간 복잡도 O(n), 공간 복잡도는 StringBuilder에 필요한 공간 때문에 O(n)
2095. Delete the Middle Node of a Linked List
Linked List의 가운데 노드를 제거하는 문제이다.
You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.
The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.
For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.
Linked List를 한 바퀴 순회해서 개수를 카운트한 다음 없애는 방법도 있지만, 더 빠른 방법은 포인터 두 개를 사용하는 방법이 있다. slow 포인터는 한 번에 한번 이동하고, fast 포인터는 한 번에 두 번 이동하면 Linked List를 한 번 순회하여 가운데 노드를 찾을 수 있다. 그런데 우리는 가운데 노드를 찾는 게 아니라 삭제해야 하기 때문에 Singly Linked List에서 가운데 노드 바로 전 노드를 찾아야 한다. 그래서 fast를 초기화할 때 head.next.next로 한 스텝 먼저 간 상태로 초기화해주고 있다.
class Solution {
public ListNode deleteMiddle(ListNode head) {
if (head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is middle node
slow.next = slow.next.next;
return head;
}
}시간복잡도 O(n), 공간복잡도 O(1)
