[LeetCode # 14 ~ 16] 문제 풀이

# 14. Longest Common Prefix

String 배열이 주어졌을 때 가장 긴 Common Prefix 를 찾는 문제

 

Common Prefix 를 찾는 방법으로 생각한 것은, 우선 문자열들을 길이 순서대로 정렬해서 가장 짧은 문자열을 공통 Prefix 로 먼저 저장을 한다. 그 다음에 순서대로 탐색을 하면서, 공통 Prefix 랑 문자열 하나씩 비교를 하고 비교했을 때 서로 같은 위치까지를 Prefix 로 저장한다. 이걸 반복하다 보면, Prefix 의 길이가 점차 짧아져서 탐색 / 비교 속도가 빠를 것이라고 생각된다.

 

string longestCommonPrefix(vector<string>& strs) {
	if (strs.empty()) {
    	return "";
    }
    
    sort(strs.begin(), strs.end());
    string prefix = strs[0];
    
    for (int i = 1; i < strs.size(); i++) {
		int l;
        for (l = 0; l < prefix.length(); l++) {
        	if (prefix[l] != strs[i][l]) {
            	break;
            }
        }
        if (l == 0) {
        	return "";
        }
        prefix = prefix.substr(0, l);
    }
    return prefix;
}

# 15. 3Sum

정수 배열이 주어졌을 때, A + B + C = 0 이 되는 Unique 한 {A, B, C} 조합을 찾는 문제

 

우선, 문제에서 주어진 배열의 Length 가 최대 3000 이라서, O(n^3) 탐색을 하게 되면 무조건 시간 초과일 것 같아서, 이걸 O(n^2) 으로 탐색할 방법을 생각하게 되었다. 그래서, A + B = 0 이 되는 두 수를 찾을 때 탐색을 최소화할 수 있는 방법을 생각해 보았는데 수를 정렬해 놓고 두 수의 합에 따라서 앞뒤 인덱스를 증가/감소 시켜가며 탐색하면 O(n) 만 탐색이 가능할 것 같았다. 그래서 세 수를 찾는 문제는, 한 수를 고정해 놓고 두 수를 찾는 방식으로 하면 고정하는 수 찾기 O(n) * 나머지 두 수 찾기 O(n) 해서 O(n^2) 에 탐색이 가능할 것으로 생각해 문제를 풀었다.

 

vector<vector<int>> threeSum(vector<int>& nums) {
	sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    
    for (int i = 0; i < nums.size(); i++) {
    	if (i > 0 && nums[i] == nums[i - 1]) {
        	continue; // 중복 제거
        }
        int left = i + 1, right = nums.size() - 1; // 왼쪽, 오른쪽 Index
        while (left < right) {
        	if (right < nums.size() - 1 && nums[right] == nums[right + 1]) {
            	right--;
                continue; // 마찬가지로 오른쪽의 값이 중복될 경우 중복 제거
            }
            
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
            	right--; // sum 이 0 보다 크면 right index 감소
            }
            else if (sum < 0) {
            	left++; // sum 이 0 보다 작으면 left index 증가
            }
            else {
            	vector<int> tmp = {nums[i], nums[left], nums[right]};
                ans.push_back(tmp);
                left++;
                right--;
            }
        }
    }
    return ans;
}

# 16. 3Sum Closest

이 문제는 #15. 3Sum 문제와 유사하지만, 차이점은 A + B + C = 0 인 위의 문제와 다르게, Target 값을 정해놓고 A + B + C = Target 에 가장 가까운 합을 구하는 데 있다.

 

그래서 이 문제를 풀 때는, 위와 마찬가지로 정렬을 하고 탐색도 동일한 방식으로 진행하지만, 세 수의 조합을 저장하지 않고 Target 값과 현재 Sum 의 차를 비교해서 기존의 차이보다 더 작게 차이가 나면 Sum 을 저장하는 방식으로 문제를 풀었다.

 

int _abs(int x) {
	return (x > 0 ? x : -x);
}

int threeSumClosest(vector<int>& nums, int target) {
	int diff = INT_MAX, ans = 0;
    sort(nums.begin(), nums.end());
    
    for (int i = 0; i < nums.size(); i++) {
    	if (i > 0 && nums[i] == nums[i - 1]){
        	continue; // 중복 제거
        }
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
        	if (right < nums.size() - 1 && nums[right] == nusm[right + 1]) {
            	k--;
                continue;
            }
            
            int sum = nums[i] + nums[left] + nums[right];
            if (_abs(sum - target) < diff) {
            	diff = _abs(sum - target);
                ans = sum;
            }
            if (sum > target) {
            	right--;
            }
            else if (sum < target) {
            	left++;
            }
            else {
            	return sum;
            }
        }
    }
    return ans;
}