(Python /LV3) 보석 쇼핑

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

풀이:

def solution(gems):
    minn,maxx = 0, 0
    res = []
    dia = {i:1 for i in set(gems)} # dia 값 0 으로 해둠
    lst = []
    now = 0
    while now < len(gems):
        for idx, i in enumerate(gems[now::],start = now+1):
            lst.append(idx)
            dia[i] -= 1
            if all (i<=0 for i in list(dia.values())):
                res.append([lst[0],lst[-1]])
                break
        lst = []
        now += 1
        dia = {i:1 for i in set(gems)}

    res.sort(key=lambda x:(x[1]-x[0],x[0]))
    return res

테스트는 1개 틀리고, 효율성에서 다 틀리는 코드이다,

계속 dia 를 만들어주고 리스트도 생성해서 그런듯하다

 

def solution(gems):
    res = []
    dia_len = len(set(gems))  # dia 값 0 으로 해둠
    sets =set()
    now = 0
    lst = []
    while now < len(gems):
        for idx, i in enumerate(gems[now::],start = now+1):
            lst.append(idx)
            sets.add(i)
            if len(sets) == dia_len:
                res.append([lst[0],lst[-1]])
                break
        lst = []
        now += 1
        sets = set()

    res.sort(key=lambda x:(x[1]-x[0],x[0]))
    return res[0]

set 으로 바꿔줬으나 정확성은 다 맞았지만, 효율성은 다 틀려버린다.

 

while문과 for 문을 같이 써서 그런것 같다.

 

def solution2(gems):
    res = []
    left, right = 0, 0
    dia_len = len(set(gems))  # dia 값 0 으로 해둠
    while right <= len(gems):
        if len(set(gems[left:right+1])) == dia_len:
            res.append([left+1,right+1])
            left += 1
        else:
            right += 1
    res.sort(key=lambda x:(x[1]-x[0],x[0]))
    return res[0]

포문을 뺏지만 효율성테스트 1개 맞는다 ,,

 

def solution(gems):
    res = []
    left, right = 0, 0
    dia_len = len(set(gems))
    gem_counts = Counter()  # 각 보석의 등장 횟수를 세는 Counter 

    while right < len(gems):
        gem_counts[gems[right]] += 1  # 보석 등장 횟수를 갱신
        if len(gem_counts) == dia_len:  # 모든 보석 종류가 포함된 경우
            while gem_counts[gems[left]] > 1:  # 최소 범위를 찾기 위해 left를 옮기면서 중복 보석을 제거
                gem_counts[gems[left]] -= 1 # 왼쪽 좌표 오른쪽으로 옮기면 왼쪽 좌표에 보석 제거
                left += 1 # 왼쪽 좌표 +1
            res.append([left+1,right+1]) # 보석을 다 포함하는 제일 작은 left, right 범위 추가
        right += 1
    res.sort(key=lambda x:(x[1]-x[0],x[0]))  # 최소 범위 기준으로 정렬
    return res[0]

 

[left : right] 

 매번 반복할 때마다 중복 계산을 수행하므로 비효율적이다

left와 right 인덱스를 이용하여 모든 가능한 서브 리스트를 탐색하여. 이는 O(N^2)의 시간 복잡도를 가지므로 효율성이 떨어진다.

 

그래서 Counter를 사용한 투 포인터 기법을 사용했다.