Daily LeetCoding Challenge for April, Day 12
문제
2차원 vector의 값을 규칙에 맞게 변경하기
아이디어
2차원 vector를 돌면서 이웃한 cell 중에서 몇개의 1이 있는지 확인한 후, 값을 정한다.
완성
submission: 6ms / 6.9MB
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int row = board.size();
int col = board[0].size();
vector<vector<int>> result(row, vector<int> (col, 0));
for(int i = 0;i < row;i++)
{
for(int j = 0;j < col;j++)
{
int sum = 0;
for(int n = i - 1;n <= i + 1;n++)
{
for(int m = j - 1;m <= j + 1;m++)
{
// 중앙 cell과 벡터의 범위를 벗어나는 cell은 제외
if ((n != i || m != j) && (n >= 0 && m >= 0 && n < row && m < col))
{
if (board[n][m] == 1)
sum++;
}
}
}
if (board[i][j] == 0)
{
if (sum == 3)
result[i][j] = 1;
else
result[i][j] = 0;
}
else
{
if (sum < 2)
result[i][j] = 0;
else if (2 <= sum && sum <= 3)
result[i][j] = 1;
else if (sum > 3)
result[i][j] = 0;
}
}
}
for(int i = 0;i < row;i++)
{
for(int j = 0;j < col;j++)
{
board[i][j] = result[i][j];
}
}
}
};
처음에는 board 자체에 값을 넣어보려고 했는데, board 값을 바꾸면 다른 cell의 상태에 영향을 주기 때문에 새로 vector를 생성해서 복사할 수 밖에 없었다. 근데 다른 사람들 코드를 보니 비트 연산을 해서 space를 O(1)로 만든 사람이 있었다. 비트 연산을 좀 더 공부해야겠다.
'ALGORITHM > c&c++ leetcode' 카테고리의 다른 글
[C++/LeetCode] Trim a Binary Search Tree (0) | 2022.04.15 |
---|---|
[C++/LeetCode] Spiral Matrix II (0) | 2022.04.13 |
[C++/LeetCode] Kth Largest Element in a Stream (0) | 2022.04.08 |
[C/LeetCode] Container With Most Water (0) | 2022.04.05 |
[C/LeetCode] Swapping Nodes in a Linked List (0) | 2022.04.04 |