청정알고리즘

문제

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

풀이

shift 연산과 더하기 빼기를 이용하여 나누기를 해본다.

우선 절댓값을 취해서 부호부분을 제외한 나머지 부분만 계산할 것인데, 이때 INT_MIN의 경우 절대값을 하면 넘어가므로, INT_MIN에 대한 처리를 진행한다.

지금 답을 출력할 수 있는 것은 출력하고, 아니라면 divisor를 한번 더해줘서 미리 한번의 덧셈을 진행해놓는다.

이제 $x/y$를 계산하는데 $b$라는 변수를 초기값 1로 따로 관리를 한다.

기본적인 알고리즘은 다음과 같다.

case 1) $x\leq y*b$

x에서 y*b를 빼내고, $ans$에 b를 더해준다. 그 후, b에 2를 곱한다.

이 때, y*b가 INT_MAX보다 커지려고 하면 곱하지 않는다.

case 2) else

이때, x가 처음의 divisor보다 작아졌을 경우, 다 나눴으므로 반복문을 종료한다.

아니라면, b에 2를 나눈다.

이 과정을 반복하면, $O(log n)$의 시간복잡도로 나누기를 할 수 있다. 

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int divide(int dividend, int divisor) {
        int ans=0;
        if(divisor==INT_MIN) return dividend==INT_MIN?1:0;
        if(dividend==INT_MIN)
        {
            if(divisor==-1) return INT_MAX;
            if(divisor==1) return INT_MIN;
            ans++;
            dividend+=abs(divisor);
        }
            
        int x=abs(dividend);
        int y=abs(divisor);
        bool sgn = (dividend<0)^(divisor<0);
        int b=1;
        while(x>0)
        {
            if(x>=y)
            {
                x-=y;
                ans+=b;
                if(y>>30) continue;
                b<<=1;
                y<<=1;
            }
            else
            {
                if(divisor>x) break;
                b>>=1;
                y>>=1;
            }
        }
        return sgn?-ans:ans;
    }
};

문제

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

풀이

문자열 내에 특정 문자열이 있는지 찾는 알고리즘으로 kmp 알고리즘이 유명하다.

이를 이용한다. 

Time Complexity : $O(n+m)$

코드

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hl = haystack.length();
        int nl = needle.length();
        if(nl==0) return 0;
        
        vector<int> fail;
        fail.resize(nl,0);
        int j=0;
        for(int i = 1; i< nl ; i++)
        {
            while(j > 0 && needle[i] != needle[j]) j = fail[j-1];
            if(needle[i] == needle[j]) fail[i] = ++j;
        }
        j=0;
        for(int i=0;i<hl;i++)
        {
            while(j>0 && haystack[i] != needle[j]) j = fail[j-1];
            if(haystack[i] == needle[j])
            {
                if(j==nl-1) return i-nl+1;
                else j++;
            }
        }
        
        return -1;
    }
};

문제

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

풀이

two pointer를 이용하여 문제를 푼다.

선행 포인터가 val이랑 다를 경우 후행 포인터의 칸에 순차적으로 채워준다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0;
        for(int j=0;j<nums.size();j++)
            if(nums[j]!=val)nums[i++]=nums[j];
        return i;
    }
};

문제

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

풀이

unique 함수를 이용하여 계산한다.

직접 구현하려면 two pointer를 이용해서 구해보자. 어렵지 않다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        return unique(nums.begin(), nums.end())-nums.begin();
    }
};

문제

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of kthen left-out nodes in the end should remain as it is.

풀이

list 문제의 연속이다.

전체 길이를 구한다음 k개씩 묶어서 각각을 뒤집는다. 뒤집는 과정은 다음과 같다.

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* reverseKGroup(ListNode* head, int k) {
        if(head==NULL || k==1)return head;
        ListNode* prev = new ListNode(0);
        prev->next = head;
        
        int l=0;
        for(ListNode* it = head; it!=NULL; it=it->next)l++;
        
        ListNode *p = prev;
        for(int i=0;i+k<=l;i+=k)
        {
            ListNode* now = p->next;
            ListNode* nxt = now->next;
            for(int j=1;j<k;j++)
            {
                now->next= nxt->next;
                nxt->next =p->next;
                p->next = nxt;
                nxt =now->next;
            }
            p=now;
        }
        return prev->next;
    }
};

문제

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