문제 링크

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

문제 설명

• 보석 리스트가 주어짐
• 모든 종류의 보석을 하나 이상 포함하는 가장 짧은 구간 리턴
• 구간이 여러 개라면 인덱스가 가장 작은 구간 리턴

풀이

• 투 포인터
  • start, end 초기화
  • 모두 포함할 경우
    • 최단 구간 갱신
    • start += 1
  • 모두 포함하지 않을 경우
    • end += 1
  • 반복

느낀 점

• 첫 시도 때 이분 탐색으로 풀어보려 안간힘을 썼는데 실패
• 나중에 다시 투 포인터로 시도해보니 알고리즘 그대로 풀려서 허무했다

코드

def solution(gems):
    answer = [-1, len(gems)]
    total = len(set(gems))
    count = {gems[0]: 1}
    s, e = 0, 0
    while True:
        # 모두 포함
        if len(count) == total:
            if answer[1] - answer[0] > e - s:
                answer[1] = e + 1
                answer[0] = s + 1
            if s == len(gems):
                break
            count[gems[s]] -= 1
            if count[gems[s]] == 0:
                del count[gems[s]]
            s += 1
        # 모두 포함 X
        else:
            if e+1 == len(gems):
                break
            if gems[e+1] in count:
                count[gems[e+1]] += 1
            else:
                count[gems[e+1]] = 1
            e += 1
    return answer