릿코드 3 - Longest Substring, 카카오 보석쇼핑

def solution(gems):
    mySet = set(gems)
    setLen = len(mySet)
    minCount = 100001
    if setLen == 1: return [1, 1]
    dic = {}
    for i in mySet:
        dic[i] = 0

    r, l = 0, 0
    dic[gems[0]] += 1
    while r < len(gems) and l < len(gems) :
        all = True
        for k, v in dic.items() :
            if v == 0 :
                all = False
                break
        if all :
            ran = r - l
            if minCount > ran :
                minCount = ran
                ans = [l+1, r+1]
                if ran == setLen-1 : return ans
            dic[gems[l]] -= 1
            l += 1

        else :
            r += 1
            if r == len(gems) : break
            else : dic[gems[r]] += 1

    return ans​

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        myDict = {}
        
        count = 0
        maxCount = 0
        if len(s) == 1 : 
            return 1
        
        for i in range(len(s)) : 
            for j in range(i, len(s)) :
                c = s[j]
                if c in myDict : 
                    break
                else : 
                    myDict[c] = True
                    count += 1
                    
            maxCount = maxCount if maxCount > count else count
            count = 0
            myDict = {}
        
        return maxCount

 

O(n^2) 의 시간복잡도를 가지는 평범한 풀이. 작년에 봤던 카카오 인턴 문제가 생각나서 한번 풀어봤다.

def solution(gems):
    setLen = len(set(gems))
    if setLen == 1:
        return [1, 1]
    minCount = 100001
    lastCur = 0
    flag = False
    save = ''
    i = 0
    while i < len(gems):

        tmp = set()
        save = gems[i]
        for j in range(i, len(gems)):
            if flag and (gems[lastCur] == gems[j] or tmp.__contains__(gems[j])):
                continue
            flag = True
            lastCur = j
            tmp.add(gems[j])
            if len(tmp) == setLen:
                ran = j - i
                if ran < minCount:
                    minCount = ran
                    ans = [i+1, j+1]
                if ran + 1 == setLen : 
                    return ans
        i += 1

    return ans

결과는 효율성 전부 실패.. 어떻게 푸는건지 너무 궁금해져서 풀이법을 한번 봤다. 정답은 투포인터로 해결..

def solution(gems):
    mySet = set(gems)
    setLen = len(mySet)
    minCount = 100001
    if setLen == 1: return [1, 1]

    dic = {}
    for i in mySet:
        dic[i] = 0

    r, l = 0, 0
    dic[gems[0]] += 1
    while r < len(gems) and l < len(gems) :
        all = True
        for k, v in dic.items() :
            if v == 0 :
                all = False
                break
        if all :
            ran = r - l
            if minCount > ran :
                minCount = ran
                ans = [l+1, r+1]
                if ran == setLen-1 :
                    return ans
            dic[gems[l]] -= 1
            l += 1
            
        else :
            r += 1
            if r == len(gems) :
                break
            else :
                dic[gems[r]] += 1

    return ans

하지만 여전히 효율성 11번부터는 아작난다. 생각을 좀 해봤는데 dic에 모든 아이템이 들어있는지 확인하는 코드가 for문으로 돌아가다보니 저 부분에서 시간을 많이 잡아먹는 거 같아서 방법을 바꿔봤다.

def solution(gems):
    setLen = len(set(gems))
    minCount = 100001
    if setLen == 1: return [1, 1]
    
    dic = {}
    dic[gems[0]] = 1
    
    r, l = 0, 0
    while r < len(gems) and l < len(gems):
        if len(dic) == setLen:
            ran = r - l
            if minCount > ran:
                minCount = ran
                ans = [l+1, r+1]
                if ran == setLen-1: return ans
            if dic[gems[l]] == 1: del dic[gems[l]]
            else: dic[gems[l]] -= 1
            l += 1

        else:
            r += 1
            if r == len(gems): break
            else:
                if not dic.get(gems[r]): dic[gems[r]] = 1
                else: dic[gems[r]] += 1

    return ans

 

후.... 드디어 클리어 했다