[Programmers][Python]보석 쇼핑

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

📌풀이

내가 쓴 풀이(성공)

• 투포인터 활용
• set을 활용해 전체 gems의 종류를 찾고, 이를 활용해 초기화한 딕셔너리 gemdict
• start, end: 범위 인덱스의 시작, 끝 값
• cnt: 초기 end의 값을 찾기 위한 변수
  • 모든 보석이 1개 이상 생길때까지 end값을 증가시킴
  • 모든 보석을 찾게 되면, 0을 가짐
  • 하나라도 없는 보석이 있으면 0이 아닌 값을 가짐
• end가 끝에 도달할때까지, start가 최대로 도달할 수 있을때까지 탐색

def solution(gems):
    total = set(gems)
    gemdict = {key:0 for key in total}  # 딕셔너리 초기화
    cnt = len(total) # 모든 보석이 있는지 판단
    length = len(gems) # gems 전체 길이
    start, end = 0, 0 # 인덱스 시작, 끝
    
    while cnt != 0: # 끝 인덱스가 처음으로 나타나는 지점 탐색
        if not gemdict[gems[end]]:
            cnt -= 1
        gemdict[gems[end]] += 1    
        end += 1
    end -= 1
    tmp = [start, end] # 처음 정답 설정
    while start <= end < length-1: # end가 끝에 도달할때까지 진행
        if not cnt : # 보석이 다 있는 경우, start값 증가
            if gemdict[gems[start]] == 1:
                cnt += 1
                gem = gems[start]
            if tmp[1]-tmp[0] > end-start:
                tmp = [start, end]
            gemdict[gems[start]] -= 1
            start += 1
        else : # 보석이 없는 경우, end값 증가
            end += 1
            if gems[end] == gem :
                cnt -= 1
                if tmp[1]-tmp[0] > end-start :
                    tmp = [start, end]
            gemdict[gems[end]] += 1
    
    while start <= end: # start를 최대한 밀 수 있을 때까지 진행
        if not cnt : # 보석이 있는 경우, start값 증가
            if gemdict[gems[start]] == 1:
                cnt += 1
            if tmp[1]-tmp[0] > end-start:
                tmp = [start, end]
            gemdict[gems[start]] -= 1
            start += 1
        else : # 보석이 하나라도 없는 경우, 마침
            break
    
    # 인덱스의 시작값이 1임을 고려
    tmp[0] += 1
    tmp[1] += 1
    return tmp

📌후기

투포인터를 이용해 해결하는 문제였는데, 아직 투포인터가 익숙하지 않아서 쉽지 않았다.... 더 많은 노력이 필요하다!