청정알고리즘

문제

Given a linked list, remove the n-th node from the end of list and return its head.

풀이

어떤 node를 지우기 위해선 그 노드의 앞 node를 알아야한다.

head node는 앞 node가 없기 때문에, 임시로 prev node를 만들어서 앞에 붙여준다.

그 후, 두개의 포인터를 관리하는데, 서로 차이가 n+1만큼 떨어지게 관리한다.

이렇게 하면 앞쪽 포인터가 NULL에 도착했을 때, 뒷쪽포인터는 지워야할 node의 앞 node를 가리키게 된다.

따라서 뒷쪽포인터를 이용하여, 삭제작업을 진행하면 된다.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * prev = new ListNode(0);
        prev->next=head;
        ListNode * n1= prev;
        ListNode * n2= prev;
        
        for(int i=0;i<=n;i++) n2=n2->next;
        while(n2)
        {
            n1=n1->next;
            n2=n2->next;
        }
        ListNode * d = n1->next;
        n1->next=n1->next->next;
        delete d;
        
        return prev->next;
    }
};

문제

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d= target? Find all unique quadruplets in the array which gives the sum of target.

풀이

3Sum과 같은 방식으로 풀이한다.

Index 두 개를 잡고, 3Sum과 같은 방식으로 계산한다.

Time Complexity : $O(n^3)$

코드

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

                    ret.push_back({nums[z],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++;
            }
            
            while(z<l-1 && nums[z+1]==nums[z]) z++;
        }
        return ret;
    }
};

문제

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

풀이

재귀함수를 이용하여 구한다.

string $s$에서 맨 앞 글자를 빼고 구성한 string을 $s'$이라고 하면

$letterCombinations(s)$ = (맨 앞글자 한 글자에 해당하는 글자 리스트) $\prod letterCombinations(s')$ 

이므로, 이 관계를 이용하여 함수를 구현한다.

Time Complexity : $O(4^|S|)$

코드

class Solution {
private:
    vector<string> let[10]={{},{},{"a","b","c"},{"d","e","f"},
                           {"g","h","i"},{"j","k","l"},
                           {"m","n","o"},{"p","q","r","s"},
                           {"t","u","v"},{"w","x","y","z"}};
public:
    vector<string> letterCombinations(string digits) {
        if(digits=="") return vector<string>();
        
        vector<string> ret(0);
        int num = digits[0]-'0';
        if(digits.length()==1)return let[num];
        
        vector<string> s=letterCombinations(digits.substr(1));
        for(int i=0;i<let[num].size();i++)
            for(int j=0;j<s.size();j++)
                ret.push_back(let[num][i]+s[j]);
        return ret;
    }
};

문제

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

문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

풀이

구현 문제이다.

나올 수 있는 모든 경우를 unordered_map에 저장하여 로마자를 key로 해당하는 숫자를 value로 저장한다.

그 후, string을 순회하면서 숫자를 모두 더한다.

코드

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string,int> a;
        a["I"]=1, a["V"]=5, a["X"]=10, a["L"]=50;
        a["C"]=100, a["D"]=500, a["M"]=1000;
        a["IV"]=4, a["IX"]=9, a["XL"]=40;
        a["XC"]=90, a["CD"]=400, a["CM"]=900;
        
        int ans=0;
        for(int i=0;i<s.length();i++)
        {
            string two=s.substr(i,2);
            if(a.find(two) != a.end()) ans += a[two], i++;
            else ans += a[s.substr(i,1)];
        }
        return ans;
    }
};

문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

풀이

구현 문제다. 잘 찍히기만 하면 되기 때문에, 다양한 방법이 있을 수 있다.

본인은 아래와 같이 roman함수를 만들어서 구현하였다.

코드

class Solution {
private:
    string roman(int num, string one, string five, string ten)
    {
        if(num==9) return one+ten;
        if(num==4) return one+five;
        
        string ret;
        if(num>=5)ret+=five;
        for(int i=0;i<num%5;i++)ret+=one;
        return ret;
    }
public:
    string intToRoman(int num) {
        int tho = num/1000;
        int hun = num/100%10;
        int ten = num/10%10;
        int one = num%10;
        
        string ret;
        return roman(tho,"M","x","x") + roman(hun,"C","D","M")
            + roman(ten,"X","L","C") + roman(one,"I","V","X");
    }
};

문제

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2

풀이

구간 [$l,r$]에 대해서 $f(l,r) = (r-l) \times \min(height[l], height[j])$를 정의한다.

그렇다면 구하고자 하는 것은 $\max(f(l,r))$이 된다.

지금은 총 $O(n^2)$의 순서쌍을 탐색해야 하지만, 약간의 성질을 이용하면 모든 순서쌍을 검사하지 않아도 된다.

1) $height[l]<height[r]$ 이라면, 임의의 $x \in [l,r]$에 대해서 $f(l,r) \geq f(l,x)$

2) $height[l]>height[r]$ 이라면, 임의의 $x \in [l,r]$에 대해서 $f(l,r) \geq f(x,r)$

1번과 2번 성질의 증명과정은 같으므로 예시로 1번 성질만 증명하겠다.

$$f(l,r)=(r-l)\times height[l]\geq(x-l)\times height[l]\geq(x-l)\times\min(height[l], height[x])=f(l,x)$$

따라서 현재 $[l,r]$을 탐색하고 있을 때, 더 나은 답은 답을 얻기 위해선, 둘 중에 더 낮은 쪽을 움직이는 것으로 정답이 될 가능성이 있는 경우를 다 둘러볼 수 있다는 말이 된다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0, r=height.size()-1, ans=0;
        while(l<r)
        {
            ans = max(ans, (r-l)*min(height[r],height[l]));
            if(height[l]<height[r])l++;
            else r--;
        }
        return ans;
    }
};

문제

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

풀이

동적계획법(Dynamic Programming)을 이용한다.

$sl, pl$을 각각 $s, p$의 길이라고 하자. 그 후 $f$를 다음과 같이 정의한다.

$f(si, pi) =$ ( $s[si:]$와 $p[pi:]$가 matching 되는지의 여부)

그러면 다음과 같은 경우로 나눌수 있다.

case 1) $pi==pl$인 경우

이 경우에는 다음 패턴이 존재하지 않으므로 현재의 s와 완벽히 매칭이 되어야 한다.

case 2) $p[pi+1]$이 '*'이 아닌 경우

이 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi+1)$이 참이면 $f(si,pi)$도 참이 된다.

나머지 경우에는 뒤쪽이 안맞거나 현재가 안 맞으므로 거짓이 된다.

case 3) $p[pi+1]$이 '*'인 경우

이 경우는 $s[i]$가 없을 수도, 여러개 나올 수도 있다.

s[i]가 없이 매칭되는 경우는 $f(si, pi+2)$가 된다. ('?*'를 제거)

s[i]가 있으면서 매칭되는 경우는 $s[si]$와 $p[pi]$가 매칭되면서 $f(si+1, pi)$가 참이어야 $f(si,pi)$가 참이 된다.

위 세가지 경우가 존재하는 모든 경우며 이를 이용해서 동적계획법을 구현하면 된다.

Time Complexity : $O(|S||P|)$

코드

class Solution {
private:
    vector< vector<int> > dp;
    int sl, pl;
    string S, P;
public:
    bool isMatch(string s, string p) {
        S=s, P=p;
        sl=s.length(), pl=p.length();
        
        dp.resize(sl+1);
        for(int i=0;i<=sl;i++)dp[i].resize(pl+1,-1);
        return f(0,0);
    }
    
    bool f(int si, int pi)
    {
        if(si>sl)return false;
        int& ret=dp[si][pi];
        if(dp[si][pi]!=-1) return ret;

        if(pi==pl) return ret=(si==sl)?1:0;
        bool match = (si<sl && (P[pi] == S[si] || P[pi]=='.'));
        if(pi+1<pl && P[pi+1]=='*')
            return ret = f(si, pi+2) || (match && f(si+1,pi));
        return ret = f(si+1, pi+1) && match;
    }
};