# 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;
}'Algorithm > LeetCode' 카테고리의 다른 글
| [LeetCode # 20 ~ 22] 문제 풀이 (0) | 2021.03.18 |
|---|---|
| [LeetCode # 17 ~ 19] 문제 풀이 (0) | 2021.03.18 |
| [LeetCode # 11 ~ 13] 문제 풀이 (0) | 2021.02.28 |
| [LeetCode # 7 ~ 9] 문제 풀이 (0) | 2021.02.26 |
| <LeetCode # 4 ~ 6> 문제 풀이 (0) | 2021.02.23 |