[프로그래머스 LV 3] 보석 쇼핑 (파이썬/python)

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

코딩테스트 연습 - 보석 쇼핑

 

처음에 최대한 짤라서 비교해보기도 해봤는데 시간초과...

 

검색해보니 투포인터 알고리즘이라는걸 사용하라한다.

카카오테크에 있는 이 설명대로 코드를 짜봤는데 ( 딱 설명에서 딕셔너리만 사용 안 함)

시간초과가 뜬다

그리고 딕셔너리를 이용해 풀면 시간초과가 뜨지 않는다.

 

리스트슬라이싱과 셋을 이용해서 푼 풀이는 투포인터 알고리즘을 쓰지 않은것만 못하다..

계속 슬라이싱해야하기때문에 그만큼 연산이 늘어날수밖에 없다.

슬라이싱 하는데 필요한 시간복잡도는 O(N)이라구 한다 덜덜

 

 

카카오테크 해설대로 딕셔너리를 이용한 풀이(합격)

def two_point(gems, len_gem):
    start = 0
    end = 0
    result = [1, len(gems)]
    dic = {}
    # 시작점이나 끝점이 구간을 벗어나면 함수 종료
    while start < len(gems) and end < len(gems):
 
        if gems[end] not in dic:
            dic[gems[end]] = 1
        else:
            dic[gems[end]] += 1
 
        if len(dic) == len_gem:
            while start <= end:
                # start에 해당하는 보석이 여러개있으면
                # start를 올려가며 최적의 값을 확인한다.
                if dic[gems[start]] > 1:
                    dic[gems[start]] -= 1
                    start += 1
                else:
                    break
            # result 에 최소거리가 짧은순
            # 시작점 빠른순으로 교체해줘야함
            # 시작점 빠른순은 알아서 정렬되어있음. 앞에서부터 올라가니까!
            if result[1] - result[0] > end - start:
                result[0] = start + 1
                result[1] = end + 1
 
        end += 1
 
    return result
 
 
def solution(gems):
    len_gem = len(set(gems))
    answer = []
 
    answer = two_point(gems, len_gem)
    
    return answer

 

 

 

 

딕셔너리 대신 리스트슬라이싱과 set을 이용한 코드 (시간초과)

def two_point(gems, len_gem):
    start = 0
    end = 0
    result = []
    # 시작점이나 끝점이 구간을 벗어나면 함수 종료
    while start < len(gems) and end < len(gems):
 
        gem = gems[start:end + 1]
 
        if len(set(gem)) == len_gem:
            if len(result) != 0:
                if result[1] - result[0] > end - start:
                    result[0] = start + 1
                    result[1] = end + 1
            else:
                # 비어있다면
                result.append(start + 1)
                result.append(end + 1)
            start += 1
        # 모든 보석을 담지 못했다면 end += 1 해줌
        else:
            end += 1
 
    return result
 
 
def solution(gems):
    len_gem = len(set(gems))
    answer = []
 
    answer = two_point(gems, len_gem)
    return answer