[2020 카카오 인턴십] 보석 쇼핑

문제 푸는 시간 : 1시간
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/67258

• 문제 정보

  • 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
  • gems 배열 크기는 1 이상 100,000 이하 => N^2 은 성립 X

• 입력

  • gems : 진열대 번호 순서대로 보석들의 이름이 저장된 배열

• 출력

  • 가장 짧은 구간의 시작 진열대 번호화 끝 진열대 번호를 차례대로 배열에 담아서 return
  • 만약 가장 짧은 구간이 여러 개인 경우 시작 진열대 번호가 가장 작은 구간을 return

• 1차 코드

  처음에는 문제를 풀 때 len(find) == count 인 순간이 당연히 end 일 것이라고 생각하고 풀었다. 그랬더니 당연히 오답 :( 뒤의 원소를 생각하지 못했던 것이 오답의 요인이였다.그래서 처음에는 while을 사용하지 않고 풀 수 있을 것이라고 생각하였는데 이 문제는 무조건 while이 필요한 문제다 => 투 포인터 !

def solution(gems):
    start, end = 1,1
    count = len(set(gems)) # 보석의 갯수
    find = {}

    if count == 1:
        return [start,end]

    for index, gem in enumerate(gems):
        if gem in find: # 이전에 존재한 보석
            find[gem] += 1
        else: # 새로운 보석
            find[gem] = 1
            if len(find) == count:
                end = index +1
                break
            else: continue

    print(find)
    for index, gem in enumerate(gems[:end]):
        find[gem] -= 1
        if find[gem] < 1 :
            start = index + 1
            return [start,end]
        else: continue

• 정답 코드

def solution(gems):
    count = len(set(gems))  # 보석의 갯수
    find = {gems[0]:1}
    start, end = 0,0
    answer = [0,len(gems)]

    if count == 1:
        return [1,1]

    while end < len(gems):
        if len(find) == count :
            if end - start < answer[1] - answer[0]:
                answer = [start, end]
            if find[gems[start]] ==1:
                del find[gems[start]]
            else:
                find[gems[start]] -=1
            start +=1
        else:
            end +=1
            if end == len(gems):
                break
            if gems[end] in find:
                find[gems[end]] +=1
            else:
                find[gems[end]] = 1
    return [answer[0]+1,answer[1]+1]