[프로그래머스] 보석 쇼핑

https://school.programmers.co.kr/learn/courses/30/lessons/67258?language=python3 

프로그래머스

 

from collections import defaultdict
def has_at_least_one(gems, selected):
    for gem in gems:
        if selected[gem] == 0:
            return False
    return True


def solution(gems):
    answer = []
    answer_len = len(gems) + 1
    gems_set = set(gems)
    
    gems_selected = defaultdict(int)
    left = 0
    for right, gem in enumerate(gems):
        gems_selected[gem] += 1
        if has_at_least_one(gems_set, gems_selected):
            while has_at_least_one(gems_set, gems_selected):
                gems_selected[gems[left]] -= 1
                left += 1
            left -= 1
            gems_selected[gems[left]] += 1
            
            if answer_len > right-left+1:
                answer_len = right-left+1
                answer = [left+1, right+1]
    return answer

보석이 종류별로 한 개씩은 있는지 확인하는 단계가 있는데 이건 보석 갯수에 의존적인 로직이다.

어차피 한 개씩만 있으면 되는건데 딕셔너리로 갯수까지 관리하고 딕셔너리 안의 원소 개수를 이용하면 보석 종류를 알 수 있는 것이다.

+ 괜히 while문은 쓰기 꺼리다 보니 ...

 

def solution(gems):
    N = len(gems)
    answer = [0, N-1]
    kind = len(set(gems))  # 보석종류
    dic = {gems[0]:1,}  # 종류 체크할 딕셔너리
    s,e = 0,0  # 투포인터
    while s<N and e<N:
        if len(dic) < kind:  # 종류 부족하면 end point 증가 & dic 개수 증가
            e += 1
            if e == N:
                break
            dic[gems[e]] = dic.get(gems[e], 0) + 1
            
        else:  # 종류 같으면 ans 비교 후 답 갱신하고, start point 증가 & dic 개수 다운
            if (e-s+1) < (answer[1]-answer[0]+1):
                answer = [s,e]
            if dic[gems[s]] == 1:
                del dic[gems[s]]
            else:
                dic[gems[s]] -= 1
            s += 1

    answer[0] += 1
    answer[1] += 1
    return answer

def solution(gems):
    size = len(set(gems))
    dic = {gems[0]:1}
    temp = [0, len(gems) - 1]
    start , end = 0, 0

    while(start < len(gems) and end < len(gems)):
        if len(dic) == size:
            if end - start < temp[1] - temp[0]:
                temp = [start, end]
            if dic[gems[start]] == 1:
                del dic[gems[start]]
            else:
                dic[gems[start]] -= 1
            start += 1

        else:
            end += 1
            if end == len(gems):
                break
            if gems[end] in dic.keys():
                dic[gems[end]] += 1
            else:
                dic[gems[end]] = 1

    return [temp[0]+1, temp[1]+1]

 

문제가 깔끔하긴 깔끔하다..

내가 찾고자 하는 것이 어떤 조건들을 가지는 건지 나누는 연습.

수도코드를 먼저 작성하는 연습.