프로그래머스 보석쇼핑 67258 파이썬

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67258

문제

#Testcase
gems = ["ZZZ", "YYY", "NNNN", "YYY", "BBB"] #[1,5]
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] #[3,7]

투포인터st로 접근하기

DIA RUBY RUBY DIA DIA EMERALD SAPPHIRE DIA 일때, DIA RUBY EMERALD SAPPHIRE가 모두 포함되는 구간을 찾는것이 문제인데

정확성과 효율성을 찾아야하는 문제다보니, 어케할까 고민하다가 슬라이딩윈도우(투포인터) 방법으로 접근해봤다

시간초과 나는 코드

def solution(gems):
    # answer = []
    # return answer

    gem_list = set(gems)
    n = len(gems) # n = 8
    i, j = 0, 1
    temp = []

    while j < n+1 :
        if set(gems[i:j]) == gem_list : 
            # print(gems[j-i, i:j])
            temp.append([j-i, i+1, j])
            i += 1
        else : 
            j += 1

    temp.sort(key=lambda x : (x[0],x[1],x[2]))
    return(temp[0][1:3])

정답은 맞는데 왜 시간초과가 날까를 생각해봤다
리스트 인덱싱을 하는 과정에서 [i:j] 가 n 이라면 O(n) 인데, 이게 너무 크고 빈번해서 그런것같다.

Dict를 써봐야할것같다

애매하게 해결한 코드

def solution(gems):

    gem_list = set(gems)
    n = len(gems) # n = 8
    i, j = 0, 0
    temp = []

    gem_dict = dict()
    for gem in gem_list :
        gem_dict[gem] = 0

    def check(gem_dict) :
        if 0 in gem_dict.values() :
            return False
        else :
            return True 

    while j < n : 
        if check(gem_dict) == False : 
            gem_dict[gems[j]] += 1
            j += 1

        else :
            temp.append([j-i,i+1,j])
            gem_dict[gems[i]] -= 1
            i += 1
    temp.append([j-i,i+1,j])

    temp.sort(key=lambda x : (x[0],x[1],x[2]))
    return(temp[0][1:3])

이렇게 풀면 87점? 정도 맞는다. 여기서 어떻게 더 고쳐야할지 아직도 모르겠다.