청정알고리즘

문제

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

문제

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

풀이

음수인 경우는 무조건 false를 return한다.

양수인 경우에는 Reverse Integer를 구해서 같은지 체크한다.

Time Complexity : $O(logn)$

코드

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        long long num=0, t=x;
        while(t)
        {
            num = num*10+t%10;
            t/=10;
        }
        return x==num;
    }
};

문제

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

풀이

우선 글의 앞에 공백이 있을 수도 있으니, 앞에 있는 공백을 전부 제거한다.

그 후 가장 첫 글자가 부호인 경우에 $sgn$변수에 부호를 저장해준다.

그리고 정답을 저장하는 변수인 $ans$에 $ans=ans*10 + str[i]-\text{'0'}$를 계속 더해주면 된다.

Reverse Integer 문제와 마찬가지로 boundary case처리를 해주면 끝난다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int myAtoi(string str) {
        int st, ans=0, sgn=1;
        for(st=0;str[st]==' '&&st<str.length();st++);
        
        if(str[st]=='-')
        {
            sgn=-1;
            st++;
        }
        else if(str[st]=='+') st++;
        
        for(int i=st;i<str.length();i++)
        {
            if(str[i]<'0' || str[i]>'9') break;
            int num = str[i]-'0';
            if(ans>INT_MAX/10 || (ans==INT_MAX/10 && num>7)) return INT_MAX;
            if(ans<INT_MIN/10 || (ans==INT_MIN/10 && num>8)) return INT_MIN;
            ans = ans * 10 + num*sgn;
        }
        return ans;
    }
};

문제

Given a 32-bit signed integer, reverse digits of an integer.

풀이

$ans$ 변수를 관리 하면서

ans = 10*ans + x%10;
x /=10;

를 반복하면 된다.

주의해야할 점은, boundary condition을 처리하는 것이다.

첫 줄을 계산할 때 INT_MAX를 넘거나 INT_MIN보다 작아지면 바로 return 해준다.

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while(x)
        {
            int num = x%10;
            x/=10;
            if(ans > INT_MAX/10 ||( ans == INT_MAX/10 && num>7))return 0;
            if(ans < INT_MIN/10 || (ans == INT_MIN/10 && num<-8))return 0;
            ans = ans*10+num;
        }
        return ans;
    }
};

문제

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P      A       H      N

  A  P   L  S   I   I   G

    Y        I        R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

풀이

$jmp=2\times \text{numRows}-2$의 주기로 반복되는 규칙이 생긴다는 것을 캐치하자.

그러면 줄별로 주기가 $jmp$가 되고, 규칙에 맞게 순서대로 출력을 하면 끝난다.

첫줄과 마지막 줄은 $jmp$마다 1개씩, 나머지 줄은 2개씩 포함된다는 것을 캐치한다면 나머지는 구현.

Time Complexity : $O(n)$  

코드

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        
        string ret;
        int l=s.size(), jmp = 2*numRows-2;
        
        for(int i=0;i<numRows;i++)
        {
            for(int j=0;j+i<l; j+=jmp)
            {
                ret += s[j+i];
                if(i!=0 && i!= numRows-1 && j+jmp-i<l) ret+=s[j+jmp-i];
            }
        }
        return ret;
    }
};

문제

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

풀이

문자열 내에서 Palindrome을 찾는 알고리즘으로 Manacher's Algorithm이 있다.

이를 이용하여 $O(n)$의 시간복잡도로 원하는 답을 찾을 수 있다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()==0)return s;
        string sm;
        sm.push_back('$');
        for(int i=0;i<s.length();i++)
        {
            sm.push_back(s[i]);
            sm.push_back('$');
        }
        
        int r=0,p=0,l=sm.length(), ans=0, ansind;
        vector<int> a(l);
        for (int i=0;i<l;i++)
        {
            a[i] = i<=r?min(a[2*p-i],r-i):0;
            while (i-a[i]-1 >= 0 && i+a[i]+1 <l && sm[i-a[i]-1] == sm[i+a[i]+1]) a[i]++;
            if (r < i+a[i]) r = i+a[i], p = i;
            if(ans<a[i]) ans=a[i], ansind=i;
        }
        return s.substr((ansind-ans)/2,ans);      

    }
};