청정알고리즘

문제

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