청정알고리즘

문제

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