[Programmers] Level 3. 보석 쇼핑

🔗 Problem Link

프로그래머스

---

❔Thinking

• 구간 내의 모든 보석을 담을 때, 모든 종류의 보석이 하나 이상 담기는 가장 짧은 구간을 반환한다.

---

💻Solution

def solution(gems):
    n = len(set(gems))
    answer = [0, len(gems)-1]
    gem = {gems[0]: 1}
    s, e = 0, 0
    while s < len(gems) and e < len(gems):
        if len(gem) == n:
            if e-s < answer[1] - answer[0]:
                answer = [s, e]
            if gem[gems[s]] > 1:
                gem[gems[s]] -= 1
            else:
                del gem[gems[s]]
            s += 1
        else:
            e += 1
            if e == len(gems):
                break
            if gems[e] in gem.keys():
                gem[gems[e]] += 1
            else:
                gem[gems[e]] = 1
    return [answer[0]+1, answer[1]+1]

---

🗝️keypoint

1. 구간을 하나씩 살피며 모든 보석이 하나 이상 담겼는지 확인하면, 시간초과가 발생한다.
2. dict에 보석과 해당 보석의 개수를 담고, dict의 크기가 보석 종류의 개수와 일치하면 조건에 맞는 구간이라 판단한다.
3. dict에 개수를 더하거나 뺄 때, 0개 일때는 dict에서 해당 보석을 제거해야 한다.
4. 보석의 종류가 0개인 min(dict.values()) == 0을 활용하면, min의 시간복잡도로 인해 시간초과가 발생한다.