반응형
# 34. Find First and Last Position of Element in Sorted Array
정렬된 정수 Array 와 Target 정수값이 주어졌을 때, 해당 Target 값이 나타나는 인덱스의 시작 위치와 끝 위치를 찾는 문제.
* O(logN) 에 해결할 수 있는지.
이 문제는 전형적인 Binary Search 로 생각해 풀었다. Binary Search 탐색을 위해 시작/끝 인덱스를 사용하고 그 값을 찾았을 경우에 left / right 값에 현재까지 찾은 값들 중 가장 작은, 큰 인덱스 값을 대입하도록 했다.
void binarySearch(vector<int>& v, int t, int s, int e, int &l, int &r) {
if (s >= e) {
if (s == e && v[s] == t) {
if (l == -1 || s < l)
l = s;
if (r == -1 || s > r)
r = s;
}
return;
}
int m = (s + e) / 2;
binarySearch(v, t, s, m, l, r);
binarySearch(v, t, m + 1, e, l, r);
}
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) {
vector<int> ans = { -1, -1 };
return ans;
}
int left, right;
left = right = -1;
binarySearch(nums, target, 0, nums.size() - 1, left, right);
vector<int> ans = { left, right };
return ans;
}# 35. Search Insert Position
중복되지 않는 정렬된 정수형 Array 가 주어졌을 때, Target 값을 주고 그 값이 존재한다면 그 인덱스 위치를, 존재하지 않으면 그 값이 들어가야 할 인덱스 위치를 찾는 문제.
이 문제도 마찬가지로 전형적인 Binary Search 문제로 생각되어 풀었는데 굳이 Binary Search 를 사용하지 않고 라이브러리 함수를 사용해 문제를 해결했다. lower_bound 를 사용했지만 중복되는 값이 없기 때문에 upper_bound 를 사용했어도 결과는 같을 것으로 생각된다.
int searchInsert(vector<int>& nums, int target) {
vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), target);
return (it - nums.begin());
}# 36. Valid Sudoku
스도쿠가 주어졌을 때, 이 스도쿠가 제대로 구성되었는지 확인하는 문제
* 이 스도쿠 문제를 해결 가능한 지를 보는 것이 아니라, 현재 상태에서 오류가 없는 지만 확인.
단순하게 문제를 해결하는 방식으로 구현했다. 각 Row, Col, Box 별로 저장되어 있는 값을 확인해서 중복되는 값이 없는 지를 확인하도록 했다.
bool check_row[9][10];
bool check_col[9][10];
bool check_box[9][10];
bool isValidSudoku(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
continue;
int r = i, c = j, b = (i / 3) * 3 + j / 3;
int val = board[i][j] - '0';
if (check_row[r][val])
return false;
if (check_col[c][val])
return false;
if (check_box[b][val])
return false;
check_row[r][val] = check_col[c][val] = check_box[b][val] = true;
}
}
return true;
}'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode # 43, 45, 46] 문제 풀이 (0) | 2021.04.01 |
|---|---|
| [LeetCode # 38 ~ 40] 문제 풀이 (0) | 2021.03.30 |
| [LeetCode # 31 ~ 33] 문제 풀이 (0) | 2021.03.21 |
| [LeetCode # 26 ~ 28] 문제 풀이 (0) | 2021.03.19 |
| [LeetCode # 23 ~ 24] 문제 풀이 (0) | 2021.03.19 |