[LeetCode # 26 ~ 28] 문제 풀이

# 26. Remove Duplicates from Sorted Array

중복값이 존재하는 정렬된 정수 배열이 주어졌을 때, 모든 값들이 한 번씩만 등장하도록 만드는 문제

 

Sorted Array 를 순차적으로 탐색하면서, 바뀌는 값이 등장할 때마다 이를 배열에 저장하는 방식으로 구현했다.

 

int removeDuplicates(vector<int>& nums) {
	if (nums.size() == 0)
		return 0;
	int i, j;
	for (i = j = 1; j < nums.size(); j++) {
		if (nums[j - 1] != nums[j]) {
			nums[i++] = nums[j];
		}
	}
	return i;
}

# 27. Remove Element

정수 배열과 Target 값이 주어졌을 때, 배열에서 해당 값을 삭제하는 문제

 

위의 문제와 유사하게, 두 개의 인덱스를 가지고 탐색을 하면서 삭제하고자 하는 값이 등장하면 그 값을 제외하고 배열에 저장하는 식으로 문제를 해결했다.

 

int removeElement(vector<int>& nums, int val) {
	int i, j;
	for (i = j = 0; j < nums.size(); j++) {
		if (nums[j] == val) {
			continue;
		}
		nums[i++] = nums[j];
	}
	return i;
}

# 28. Implement strStr()

두 문자열이 주어졌을 때, 부분 문자열의 시작 위치를 찾는 문제

 

본래 문자열에서 찾고자 하는 부분 문자열의 길이만큼 Substr 을 저장하고, 슬라이딩 윈도우 방식으로 앞의 문자를 빼고 뒤의 문자를 빼면서 부분 문자열과 비교를 해서 위치를 찾는 방식으로 문제를 해결했다.

 

int strStr(string haystack, string needle) {
	if (needle.size() > haystack.size())
		return -1;
	else if (needle.size() == haystack.size() && needle != haystack)
		return -1;

	string comp;
	int i;
	comp = haystack.substr(0, needle.size());
	if (comp == needle)
		return 0;
	for (i = 1; i + needle.size() - 1 < haystack.size(); i++) {
		comp = comp.substr(1) + haystack[i + needle.size() - 1];
		if (comp == needle)
			return i;
	}
	return -1;
}