청정알고리즘

문제

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

    }
};

문제

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

풀이

전형적인 binary search 문제이다.

$l1=nums1.size(), l2=nums2.size()$라고 하자.

$nums1$에서 binary search를 돌리는 데 찾는 것은 다음과 같다.

'$nums1[i]$보다 작거나 같은 숫자가 $nums1, nums2$ 합쳐서 $(l1+l2+1)/2$ 개 이상이 되는 최소한의 index i'

현재 $nums1$에서의 index를 $m_1$이라고 하면 해당하는 $nums1[m_1]$보다 작은 숫자가 $nums1$에는 $m_1$개 있을 것이다.

따라서 $nums2$에 $m_2=(m1+m2+1)/2 - m_1$개가 있어야 한다.

리스트의 상황을 간단히 그리면 다음과 같다.

nums1[0]    nums1[1]   ...   nums1[$m_1-1$] |||  nums1[$m_1$]  ... 

nums2[0]    nums2[1]   ...   nums2[$m_2-1$] |||  nums2[$m_2$]   ...

각 list가 정렬되어 있음은 주어진 조건이므로 우리는

$nums2[m_2-1] <= nums1[m_1]$과 $nums1[m_1-1] <= nums2[m_2]$만 체크하면 충분하다.

첫번째 조건을 만족하지 못하면 $nums1[m_1]$이 너무 작다는 뜻이니, $m_1$을 증가시켜주면 되고

두번째 조건을 만족하지 못하면 반대로 $nums1[m_1]$이 너무 크다는 뜻이니 $m_1$을 감소시켜주면 된다.

이 조건을 이용하여 binary search를 진행하여 중간값을 찾는다.

그렇게 하면 |||로 나누어진 구간 왼쪽과 오른쪽에 숫자가 반반씩 있게 되고,

홀짝을 비교하여 ||| 앞뒤에 있는 4개의 숫자를 단순계산하여 중간값을 찾을 수 있다.

Time Complexity : $O(log(n+m))$

코드

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        vector& n1=(nums1.size()<nums2.size()?nums1:nums2);
        vector& n2=(nums1.size()<nums2.size()?nums2:nums1);
        
        int l1 = n1.size(), l2=n2.size();
        int l=0, r=l1, midnum = (l1+l2+1)>>1;
        while(l<=r)
        {
            int m1 = (l+r)>>1;
            int m2 = midnum-m1;
            if(m1>r && n2[m2-1]>n1[m1]) l = m1+1;
            else if( m1>l && n1[m1-1]>n2[m2]) r=m1-1;
            else
            {
                int ans;
                if(m1==0) ans=n2[m2-1];
                else if(m2==0) ans=n1[m1-1];
                else ans = max(n1[m1-1], n2[m2-1]);
                if((l1+l2)&1) return ans;
                
                int ans2;
                if(m1==l1) ans2 = n2[m2];
                else if(m2==l2) ans2= n1[m1];
                else ans2 = min(n1[m1], n2[m2]);
                return (ans+ans2)/2.0;
            }
        }
        return 0.0;
    }
};

문제

Given a string, find the length of the longest substring without repeating characters.

풀이

Sliding Window 방식을 사용한다. 

반복되는 문자가 없는 Window를 계속 관리해준다.

새 문자가 window에 추가될 때, 이 문자가 window에 없는 문자면 그냥 window를 늘려가면 되고,

이미 등장한 문자면 현재 추가될 문자의 가장 최신 위치를 찾아서, 그 앞까지를 새로운 window로 정하면 된다.

이를 빠르게 계산하기 위해 알파벳별로 최근에 등장한 위치를 저장해두면서 관리한다.

이를 계산해놓으면 새 문자가 추가될때, 해당하는 window를 O(1)에 계산할수 있다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l=s.length(),ans=0;
        int index[128]={0,};
        
        for(int i=0,j=0;j<l;j++)
        {
            i = max(index[s[j]],i);
            ans = max(ans, j-i+1);
            index[s[j]] = j+1;
        }
        return ans;
    }
};