283. Move Zeroes
- 타깃이 0이면 뒤로 보내준 뒤 right++, 타깃이 0이 아니면 그대로 둔 뒤 left++ 해서 탐색 범위를 줄여준다.
- 시간복잡도는 O(n^2), shift할 때마다 O(n)만큼의 이동이 발생하기 때문이다.
public void moveZeroes(int[] nums) {
int right = nums.length;
int left = 0;
while (left != right) {
if (nums[left] == 0) {
for (int i = left; i < right - 1; i++) {
nums[i] = nums[i + 1];
}
nums[right - 1] = 0;
right--;
} else {
left++;
continue;
}
}
System.out.print(nums);
}
- Two pointers를 사용하면 O(n)에 해결이 가능하다.
- 타깃이 0이 아닐 경우 삽입할 위치 (pos)에 해당 원소를 넣은 후 삽입 위치를 증가시켜서 다음 삽입할 곳으로 이동해준다. (pos++)
- 즉, 현재 삽입해야하는 위치에 타깃이 0인지 아닌지를 판별한 후 덮어씌워주는 것이다.
- 0이 아닌 값들을 먼저 앞으로 모아둔 뒤 pos부터 끝까지 0으로 채워준다.
public void moveZeroes(int[] nums) {
int pos = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] != 0) nums[pos++] = nums[i];
}
while(pos < nums.length) nums[pos++] = 0;
System.out.print(nums);
}
- 위와 같이 같은 방향 투포인터인데, 선택정렬처럼 구현해서 앞쪽에 0이 아닌 숫자를 모아주고 0들이 뒤로 가게 만드는 방식도 가능하다.
public void moveZeroes(int[] nums) {
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[i];
nums[i] = nums[pos];
nums[pos] = temp;
pos++;
}
}
}
note
- 두 개의 포인터 (인덱스)를 사용하면 O(n^2)이 걸리는 작업을 O(n)에 해결이 가능하다.
- 같은 방향 투 포인터 fast-slow pointers
- 반대 반향 투 포인터 two-pointer converging가 있다.
392. Is Subsequence
- Subsequence (부분 수열)은 스택 괄호찾기 문제처럼 모든 원소가 있어야할 뿐만 아니라 순서가 보장되어야 한다.
- 시간 복잡도 O(n)
public boolean isSubsequence(String s, String t) {
int pointer_s = 0;
int pointer_t = 0;
if (s.equals("")) return true;
if (t.equals("")) return false;
while(pointer_s != s.length() && pointer_t != t.length()){
while(s.charAt(pointer_s) != t.charAt(pointer_t)) {
pointer_t++;
if(pointer_t == t.length()) return false;
}
pointer_s++;
pointer_t++;
}
return pointer_s == s.length()
}
- 반복문을 수정해서 문자열이 비어있는지 점검하는 부분과 내부 while문을 없앨 수 있다.
- 비교하기 위한 단순 순회 포인터는 i로, 매칭되는 위치를 추적하는 포인터는 pos로 의미를 부여해서 구분하면 이해하기에 좋다.
public boolean isSubsequence(String s, String t) {
int pos = 0;
for (int i = 0; i < t.length() && pos < s.length(); i++) {
if (s.charAt(pos) == t.charAt(i)) {
pos++;
}
}
return pos == s.length();
}
11. Container With Most Water
- left와 right를 비교해서 더 작은 쪽을 옮겨줬다.
- 넓이는 결국 낮은 쪽의 높이를 따르기 때문에 낮은 값을 높여주는 방식으로 넓이의 최대값을 찾아야한다.
public int maxArea(int[] height) {
int result = 0;
int left = 0;
int right = height.length - 1;
while(left < right){
int current = (right - left) * Math.min(height[left], height[right]);
result = Math.max(result, current);
if(height[left] < height[right]) left++;
else right--;
}
return result;
}
- 현재 높이보다 같거나 낮은 벽은 넓이가 커질 수 없으니 건너뛰어서 약간의 효율을 높일 수 있다.
public int maxArea(int[] height) {
int result = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int currentH = Math.min(height[left], height[right]);
result = Math.max(result, (right - left) * currentH);
while (left < right && height[left] <= currentH) left++;
while (left < right && height[right] <= currentH) right--;
}
return result;
}
1679. Max Number of K-Sum Pairs
- disjoint pairs : 서로소 쌍
- 해시맵으로 페어가 되는 값이 있는지 판별
public int maxOperations(int[] nums, int k) {
HashMap<Integer, Integer> m = new HashMap<>();
int result = 0;
for(int num : nums){
if(m.containsKey(k - num)) {
result++;
m.put(k - num, m.get(k - num) - 1);
if(m.get(k - num) == 0) m.remove(k - num);
} else {
if(m.containsKey(num)) m.put(num, m.get(num) + 1);
else m.put(num, 1);
}
}
return result;
}
- key가 있으면 value를, 없으면 default value를 반환하는
getOrDefault를 사용해서 효율성과 가독성을 높일 수 있다. containsKey+get: 해시 탐색 2번,getOrDefault: 해시 탐색 1번
public int maxOperations(int[] nums, int k) {
HashMap<Integer, Integer> m = new HashMap<>();
int result = 0;
for (int num : nums) {
if (m.getOrDefault(k - num, 0) > 0) {
result++;
m.put(k - num, m.get(k - num) - 1);
} else {
m.put(num, m.getOrDefault(num, 0) + 1);
}
}
return result;
}
- Array.sort() 정렬 후 투포인터를 하는 방법도 가능하다.
- 정렬할 때 O(n^2) 경우가 우려됐는데, 극단적인 경우가 아니면 O(n log n) 이라서 원시 타입, 물리적으로 연속된 배열을 사용한 방식이 일반적으로 더 빠르다.
- HashMap의 실제 연산 비용(상수 계수)이 더 클 수 있다.
GitHub Comments