[LeetCode # 34 ~ 36] 문제 풀이

# 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;
}