청정알고리즘

문제

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

풀이

기본적인 list 구현문제이다.

적당한 list 연산을 이용해서, 위의 list를 아래와 같이 변형시켜주는 계산을 진행한다.

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* swapPairs(ListNode* head) {
        ListNode* prev = new ListNode(0);
        prev->next=head;
        for(ListNode *it=prev; it!=NULL;)
        {
            if(it->next==NULL || it->next->next==NULL) break;
            ListNode *temp=it->next;
            it->next=it->next->next;
            temp->next = it->next->next;
            it->next->next=temp;
            it=temp;
        }
        return prev->next;
    }
};

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

풀이

우리는 Merge Two Sorted Lists를 알고있다고 가정하자.

그렇다면 분할정복을 이용해서 문제를 해결할 수 있다.

list를 절반으로 나눠서 각각의 Merge k/2 Sorted Lists를 구한 다음, 이 두 list를 Merge Two Sorted Lists로 합치면 끝.

시간복잡도를 $T(list)$이라 한다면 $T(list)=T(l)+T(r)+O(|N|)$이므로 $T(list)=O(|N|logk)$이다.

(여기서 |N|은 총 노드의 수, k는 list의 원소의 수)

Time Complexity : $O(|N|logk)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
    ListNode* merge(int l, int r, vector<ListNode*>& lists)
    {
        if(l==r) return NULL;
        if(l+1==r) return lists[l];
        int mid=(l+r)/2;
        return mergeTwoLists(merge(l,mid,lists), merge(mid,r,lists));
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(0,lists.size(),lists);
    }
};

문제

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

풀이

분할정복법으로 풀이가 가능하다.

임의의 괄호열은 "( 괄호열1 ) 괄호열2" 꼴로 나타낼 수 있다.

또한 괄호열1과 괄호열2를 만드는 것은 전체문제의 subproblem이기 때문에 분할정복법이 가능한 것이다.

괄호열1이 $i$쌍의 괄호열이라면 총 $n$쌍이기 때문에, 괄호열2는 $n-1-i$쌍이 된다.

또한, 임의의 괄호열에 대해서 i값은 유일하게 정해진다.

따라서, 0부터 n-1까지의 i에 대해서, generateParenthsis(i)와 generateParenthesis(n-1-i)를 구한다.

각각 구한 쌍에 대해서, 모든 "( 괄호열1 ) 괄호열2"의 조합을 만들면 된다.

정답을 모두 구해야하기 때문에 시간복잡도는 정답 개수에 binding 된다.

괄호열의 개수는 n번째 카탈란 수라는 것이 알려져 있다.

Time Complexity : $O( |ans| )$

코드

class Solution {
private:
    string lp = "(";
    string rp = ")";
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        if(n==0) ans.push_back("");
        else for(int i=0;i<n;i++)
            for(string l: generateParenthesis(i))
                for(string r:generateParenthesis(n-1-i))
                    ans.push_back(lp+l+rp+r);
        return ans;
    }
};

문제

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

풀이

list에 대한 기본 구현을 묻는 문제이다. Merge Sort에 대한 기본적인 지식이 있다면 어렵지 않게 풀수 있다.

각각의 list가 정렬되어 있으므로, 가장 작은 숫자는 l1[0](그냥 array notation으로 쓰겠다.)과 l2[0]중에 작은 것이 된다.

그 후 그 작은걸 list에서 제거하면, 다시 처음과 같은 상황이 되고 l1[0]과 l2[0]중에 작은 숫자를 찾으면 된다.

이를 계속해서 반복하여, 제거되는 숫자들을 모으면 정렬된 리스트를 만들 수 있다.

Time Complexity : $O(|l1|+|l2|)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
};

문제

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

풀이

Valid Parenthese를 판별하는 문제는 스택(Stack) 자료구조를 사용하는 문제로 유명하다.

문자열을 순서대로 돌면서 여는 괄호가 나오면 죄다 스택에 넣는다.

닫는 괄호가 나오면 스택에서 가장 위의 원소와 현재 닫는 괄호가 매칭이 되는 지를 체크한다.

만약 이때, 스택이 비어있거나 매칭이 되지 않으면 Invalid하므로 바로 false를 return한다.

마지막으로 문자열을 다 계산한 후에, 스택이 비어있으면 올바른 괄호열이 된다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    bool isValid(string s) {
        stack<char> S;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
            {
                S.push(s[i]);
                continue;
            }
            if(S.empty())return false;
            if(s[i]==')' && S.top()!='(') return false;
            if(s[i]==']' && S.top()!='[') return false;
            if(s[i]=='}' && S.top()!='{') return false;
            S.pop();
        }
        return S.empty();
    }
};

문제

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