알고리즘 스터디 2주차

LeetCode Top Interview Questions [Medium Collection]

Array and Strings

Longest Substring Without Repeating Characters

Explore - LeetCode

접근 방식

Set이나 map등에 넣어서 중복을 찾는다.
1. Index를 캐싱 해두었다가, 중복이 검출되면 해당 Index부터 시작
2. TowPointer을 사용해서 줄이는 방식 사용

Index를 캐싱 해두었다가, 중복이 검출되면 해당 Index부터 시작

606ms(5.13%)…

O(n^2)

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_set<char> array;
        int answer = 0, lenth = 0;
        int cachedIndex = 0;

        for (int i = 0; i < s.length();)
        {
            auto iter = array.find(s[i]);
            if (iter == array.end())
            {
                lenth++;
                if (lenth == 2)
                {
                    cachedIndex = i;
                }
            }
            else
            {
                answer = max(answer, lenth);
                lenth = 1;
                array.clear();
                i = cachedIndex++;
            }
            array.insert(s[i]);
            i++;
        }

        answer = max(answer, lenth);
        return answer;
    }
};

TowPointer

좌, 우 포인터를 만들어서 한쪽으로 가다가 중복을 만나면 반대쪽 포인터를 줄여 검사를 최소화 하게 수정

19ms 30.52%

평균 - O(n)

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_set<char> seen;
        int ans = 0, length = 0;
        int L = 0;

        for (int R = 0; R < s.size(); ++R)
        {
            while (seen.count(s[R]))
            {
                seen.erase(s[L++]);
                length--;
            }
            seen.insert(s[R]);
            ans = max(ans, length + 1);
            length++;
        }
        return ans;
    }
};

Longest Palindromic Substring

Explore - LeetCode

접근 방식

투포인터를 사용 해서, 특정 문자에서 좌우로 뻗어가면 될것 같다.

투포인터

O(2n)

Runtime : 20ms 53.74% Memory : 35.3MB 29.24%

class Solution
{
public:
    string longestPalindrome(string s)
    {
        string ans;

        for (int centerIndex = 0; centerIndex < s.size(); ++centerIndex)
        {
            int L = centerIndex, R = centerIndex;
            while (L - 1 >= 0 && s[centerIndex] == s[L - 1])
            {
                L--;
            }

            while (R + 1 <= s.size() && s[centerIndex] == s[R + 1])
            {
                R++;
            }

            while (L - 1 >= 0 && R + 1 <= s.size() && s[L - 1] == s[R + 1])
            {
                L--;
                R++;
            }

            int len = R - L + 1;

            ans = ans.size() > len ? ans : s.substr(L, R - L + 1);
        }
        return ans;
    }
};

개선

substr을 너무 많이해서 len, index만 얻은 뒤에 마지막에 substr하면 개선이 될것 같음.

Runtime : 3ms 97.90% Memory : 9.3MB 82.01%

O(n)

class Solution
{
public:
    string longestPalindrome(string s)
    {
        int bestL = 0, bestLen = 0;

        for (int centerIndex = 0; centerIndex < s.size(); ++centerIndex)
        {
            int L = centerIndex, R = centerIndex;
            while (R + 1 < s.size() && s[R + 1] == s[centerIndex])
                R++;

            while (L - 1 >= 0 && R + 1 < s.size() && s[L - 1] == s[R + 1])
            {
                L--;
                R++;
            }

            if (R - L + 1 > bestLen)
            {
                bestLen = R - L + 1;
                bestL = L;
            }
        }
        return s.substr(bestL, bestLen);
    }
};

Increasing Triplet Subsequence

Explore - LeetCode

접근 방식

백준의 가장 긴 증가하는 부분 수열 이 생각나서 그에 맞게 풀었음.

array에 담고, 그것보다 큰 수가 들어왔으면 뒤에 추가, 낮은 수가 들어오면 대치한다.
lower_bound 사용

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장

LIS(최장 증가 부분수열)

Runtime : 6ms 15.77% Memory : 115.5MB 98.08%

O(n log n)

class Solution
{
public:
    bool increasingTriplet(vector<int> &num)
    {
        vector<int> tails;
        for (int x : num)
        {
            auto it = lower_bound(tails.begin(), tails.end(), x);
            if (it == tails.end())
            {
                if (tails.size() >= 2)
                    return true;
                tails.push_back(x);
            }
            else
            {
                *it = x;
            }
        }
        return false;
    }
};

PREVIOUS알고리즘 스터디 1주차

NEXT알고리즘 스터디 3주차