청정알고리즘

문제

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

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

풀이

list를 순회하면서 실제 덧셈을 하는 것 같이 계산을 해준다.

받아올림할 변수인 carry를 잘 관리하는 것이 핵심.

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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry=0;
        ListNode *ans=new ListNode(0);
        ListNode *p=l1;
        ListNode *q=l2;
        ListNode *now=ans;
        while(p!=NULL || q!=NULL)
        {
            int s =(p?p->val:0)+(q?q->val:0)+carry;
            carry = s/10;
            now->next = new ListNode(s%10);
            now = now->next;
            if(p) p=p->next;
            if(q) q=q->next;
        }
        if(carry) now->next = new ListNode(carry);
        return ans->next;
    }  
};

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

풀이

해쉬맵을 이용해서 nums에 있는 모든 숫자들을 (숫자, index) pair로 저장한다.

그 후 nums를 모두 돌면서, 합이 target이 되는 원소가 nums에 존재하는 지를 찾으면 끝난다.

주의할점은 index를 확인하면서 현재 index와 더할 숫자의 index가 다른것을 체크해 주어야한다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map<int,int> m;
        vector ret;
        for(int i=0;i<nums.size();i++) m[nums[i]]=i;
        
        for(int i=0;i<nums.size();i++)
        {
            int t = target-nums[i];
            if(m.find(t)!=m.end() && m[t]!=i)
            {
                ret.push_back(i);
                ret.push_back(m[t]);
                return ret;
            }
        }
        return nums;
    }
};