청정알고리즘

문제

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

풀이

3Sum 문제와 기본적으로 알고리즘은 동일하다.

반복하는 동안 해야할 일만 조금 다르다.

현재의 합이 지금까지 찾은 답보다 target에 가까운지 체크하고, 가까우면 갱신해주는 것 뿐이다.

Time Complexity : $O(n^2)$

코드

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        
        int l = nums.size();
        int ans=nums[0]+nums[1]+nums[2];
        for (int i=0;i<l-2;i++)
        {
            int j=i+1, k=l-1;
            while(j<k)
            {
                int sum = nums[i]+nums[j]+nums[k];
                int dis = abs(sum-target);
                if(abs(sum-target)<abs(ans-target)) ans=sum;
                    
                if(sum==target) return target;
                if(sum>target)k--;
                else j++;
                
            }
        }
        return ans;
    }
};

문제

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

풀이

숫자 $nums[i]$를 하나 고르고, 구간 $[i+1, l)$에서 합이 $-nums[i]$인 쌍 $(j,k)$를 구하면 된다.

Container With Most Water문제와 비슷하게 하나의 $nums[i]$에 대해서는 양쪽에서 범위를 좁혀가면서 구한다.

$sum=nums[i]+nums[j]+nums[k]$의 부호에 따라서 경우가 나뉘게 된다.

case 1) $sum>0$

$num[k]$가 너무 큰 것이므로, k를 1 감소시킨다.

case 2) $sum<0$

$num[j]$가 너무 작은 것이므로, j를 1 증가시킨다.

case 3) $sum=0$

해답을 찾았다. 현재의 {$nums[i], nums[j], nums[k]$}를 정답 vector에 추가해준다.

중복을 제거하기 위해서, 현재 $nums$값과 다른 새로운 값이 나올때 까지 j값을 증가시켜준다.

현재 j에 대한 $sum$은 양수이므로, 같은 방법으로 새로운 값이 나올때 까지 k값을 감소시켜준다.

이러한 방법으로 특정 i에 대해서 $nums[j]$와 $nums[k]$의 순서쌍을 $O(n)$만에 구할 수 있다.

또한 i가 총 $O(n)$개 존재하므로, 시간복잡도는 $O(n^2)$이다.

Time Complexity : $O(n^2)$

코드

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &nums) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        int l = nums.size();
        for (int i=0;i<l-2;i++)
        {
            int j=i+1, k=l-1;
            while(j<k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0){k--; continue;}
                if (sum < 0){j++; continue;}
                
                ret.push_back({nums[i],nums[j],nums[k]});
                while(j<l-1 && nums[j+1]==nums[j]) j++;
                while(k>0 && nums[k-1]==nums[j]) k--;
                j++;k--;
            }
            while(i<l-1 && nums[i+1]==nums[i]) i++;
        }
        return ret;
    }
};

문제

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

풀이

한 string을 기준으로 다른 모든 string의 i번째 글자가 전부 같은지 체크한다.

전부 같다면 계속해서 다음 글자를 확인하고, 다른 것이 있다면 현재까지의 답을 출력한다.

Time Complexity : $O(|S|)$

코드

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0 || strs[0].length()==0)return "";
        
        for(int i=0;i<strs[0].length();i++)
            for(int j=1;j<strs.size();j++)
                if(i>=strs[j].length() || strs[0][i] != strs[j][i])
                    return strs[0].substr(0,i);
            
        
        return strs[0];
    }
};