[Two pointer] [카카오 인턴] 보석 쇼핑 (프로그래머스 강의)

문제

https://school.programmers.co.kr/learn/courses/14760/lessons/125468

본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.

• 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.

  진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하기

• 진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

• 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

풀이

본 문제는 투 포인터를 사용해서 구현했다.

• 해당 문제의 해설 강의를 보기 전 먼저 코드를 구현해봤는데, 이때 두 가지 아이디어를 떠올려 구현했다. 물론 해당 두 가지 방법은 모두 시간초과 또는 테스트 케이스 실행결과의 오류를 나타내는 코드였다. 해당 아이디어가 무엇이었는지와 왜 틀렸는지에 대해 설명하고자 한다.

추후 보완 예정

코드

import collections
def solution(gems):
    answer = []
    hash = collections.defaultdict(int)
    length = len(set(gems))     # 중복되지 않는 보석의 종류 개수
    left = 0        # left pointer의 첫 시작점
    max_length = 100000     # 최대 길이는 보석의 개수로 설정
    
    for right in range(len(gems)):
        hash[gems[right]] += 1      # 보석(키 값)에 대한 개수(value)를 증가시킴
        while(len(hash) == length):     # hash 길이가 (=key값의 개수가) length개 일때만 실행
            if right-left+1 < max_length:       # max_length 갱신이 가능한 경우, 새로운 값으로 바꿔줌
                max_length = right-left+1       # 최대 길이와 이때의 구간 저장
                answer = [left+1, right+1]
                
            hash[gems[left]] -= 1           # left를 오른쪽으로 한칸씩 옮기면서 이동이 가능한지 파악
            if hash[gems[left]] == 0:       # 해당 키 값의 value가 0이면, 해당 키를 삭제
                del hash[gems[left]]
            left += 1                       # 키가 삭제되지 않았다면, left를 오른쪽으로 이동시킴
    return answer

실행 결과

• 정확성 테스트 및 효율성 테스트