리트코드 75 14일 차. Two pointers 1문제, 해시맵 1문제, 스택 1문제를 풀어봤다.
1679. Max Number of K-Sum Pairs
정수 배열 nums와 정수 k가 주어졌을 때, 배열에서 2개의 숫자 합이 k가 되는 숫자를 찾고 배열에서 삭제한다. 배열 상에서 위 작업을 할 수 있는 최대 횟수를 리턴하라.
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
문제에서 구하고자 하는 답은 결국 2개 숫자의 합이 k가 되는 숫자가 몇 쌍이나 존재하는지 찾아내는 것이다. nums 배열을 순회하면서 정수 n에 대해 k-n이 맵에 존재하는지 확인한다. 존재한다면 둘은 합이 k가 되는 한 쌍이다. 그렇지 않으면 맵에 저장하고, 출현 횟수를 업데이트해 준다. 출현 횟수를 추가해 주는 이유는 각 숫자가 배열에서 유일한 값이 아닐 수 있기 때문이다.
class Solution {
public int maxOperations(int[] nums, int k) {
int pairs = 0;
Map<Integer, Integer> freqMap = new HashMap<>();
for(int n : nums) {
if (freqMap.containsKey(k-n)) {
int freq = freqMap.get(k-n);
pairs++;
if (freq == 1) {
freqMap.remove(k-n);
} else {
freqMap.put(k-n, freq-1);
}
} else {
int freq = freqMap.getOrDefault(n, 0);
freqMap.put(n, freq+1);
}
}
return pairs;
}
}시간 복잡도는 O(n), 공간 복잡도 O(n)
2352. Equal Row and Column Pairs
n x n 정수 배열이 있을 때 행 r_i와 열 c_j가 같은 (r_i, c_j)의 수를 리턴하라. 행과 열이 동일한 값을 동일한 순서로 가지는 경우 행과 열 쌍을 같다고 한다.
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
처음에 생각해 낸 솔루션은 Brute force로 n x n 배열의 원소를 순회하면서 행과 열이 같은 값을 갖는지 확인했다. 이 경우 시간 복잡도는 O(n^3)라서 더 나은 솔루션이 있을 거라 생각했는데, 딱히 떠오르지 않았다. 어쩔 수 없이 솔루션을 봤는데, Brute force의 경우 1개의 행을 다른 열과 비교할 때 중복으로 행을 만들어서 비교하고 있었다. 그래서 해시맵을 사용하여 행을 문자열로 만들어서 키로 사용할 수 있게 만든 다음 값으로 출현 빈도를 저장해 줬다. 그다음 열을 문자열로 만들어서 행과 일치하는 값이 있는지 확인하고, 있다면 빈도수만큼 쌍이 있는 것이기 때문에 정답에 더해준다.
class Solution {
public int equalPairs(int[][] grid) {
int len=grid.length, ret=0;
Map<String, Integer> rowFreq = new HashMap<>();
for(int[] row : grid) {
String rowStr = Arrays.toString(row);
int freq = rowFreq.getOrDefault(rowStr, 0);
rowFreq.put(rowStr, freq+1);
}
for(int i=0; i<len; i++) {
int[] colArray = new int[len];
for(int j=0; j<len; j++) {
colArray[j] = grid[j][i];
}
String colStr = Arrays.toString(colArray);
if (rowFreq.containsKey(colStr)) {
ret += rowFreq.get(colStr);
}
}
return ret;
}
}Map을 이용해서 행 또는 열을 저장하는 경우, O(n^2) 시간 복잡도로 구현이 가능하다. 그리고 공간 복잡도는 O(n^2)가 된다.
735. Asteroid Collision
asteroids 배열의 각 정수는 소행성을 나타낸다. 각 소행성의 절댓값은 크기를 나타내고 부호는 방향을 나타낸다. +인 경우 오른쪽, -인 경우 왼쪽으로 이동한다. 각 소행성이 같은 속도로 이동한다. 두 소행성이 만났을 때 작은 건 폭발한다. 두 소행성의 크기가 같다면 둘 다 폭발한다. 두 소행성의 방향이 같다면 둘은 절대 만날 수 없다. 모든 폭발 뒤에 남은 소행성의 상태를 리턴하라.
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
소행성이 충돌하지 않는 경우를 먼저 생각해 보자. [-5, 10]인 경우 두 소행성은 반대 방향으로 이동하기 때문에 충돌하지 않는다. 또 [5, 5]인 경우도 같은 방향으로 이동하기 때문에 충돌하지 않는다. 그러면 충돌하는 경우는 부호가 +, - 인 소행성이 있을 때로 볼 수 있다. 충돌 후 소행성의 크기가 줄어들진 않기 때문에 한 번 충돌하고 이후에도 충돌하는 경우가 있는지 확인할 필요가 있다. 그래서 스택을 이용해서 가장 마지막에 출현한 소행성과 나머지 소행성들이 충돌하는지 확인해 준다.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> s = new Stack<>();
for(int n : asteroids) {
s.push(n);
while (s.size() > 1) {
int top = s.pop();
int under = s.pop();
if (top < 0 && under > 0) { // collision
if (Math.abs(top) > under) {
s.push(top);
} else if (Math.abs(top) < under) {
s.push(under);
}
} else {
s.push(under);
s.push(top);
break;
}
}
}
int[] ret = new int[s.size()];
for(int i=s.size()-1; i>=0; i--) {
ret[i] = s.pop();
}
return ret;
}
}시간 복잡도 계산이 어렵다.. 스택에 배열의 값을 넣으면서 한번 순회를 하는데, while문을 돌면서 충돌이 있는지 확인하고 있다. 충돌이 있는 경우 해당 소행성은 스택에 들어갔다 나갔다 두 번, 충돌이 없는 경우도 많아야 스택에 들어갔다 나갔다 두 번이기 때문에 O(2n) => O(n)이 시간 복잡도가 될 것 같다. 그리고 공간 복잡도는 n개 원소를 스택에 저장해야 하기 때문에 O(n)이 된다.
