[프로그래머스][KAKAO_인턴][2020] 보석 쇼핑

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 보석 쇼핑

 

내가 작성한 코드

from collections import Counter

def solution(gems):
    cnt = Counter([])
    N = len(set(gems))
    answer = [1, len(gems)]
    candidates = []
    start, end = 0, 0
    cnt[gems[end]] += 1
    while start <= end and end < len(gems):
        # 1. set의 개수로만 판단한다
        if len(cnt) == N:
            candidates.append([start, end])
            cnt[gems[start]] -= 1
            # cnt += Counter()는 시간초과
            # 0을 정리하는 과정에서 Counter의 크기만큼 시간이 소요되는듯
            if cnt[gems[start]] == 0 :
                del cnt[gems[start]]
            start += 1
        else:
            end += 1
            if end < len(gems):
                cnt[gems[end]] += 1

    for start, end in candidates:
        if end - start < answer[1] - answer[0]:
            answer = [start + 1, end + 1]
    return answer

• 투포인터
  
  • 모든 종류의 보석을 담는 시작과 끝을 탐색
  • 범위에 조건이 만족할 경우 시작이 증가
  • 범위에 조건이 만족하지 않을 경우 끝이 증가

 

다른 사람이 작성한 코드

from collections import defaultdict


def solution(gems):
    answer = [0, 0]
    candidates = []
    start, end = 0, 0
    gems_len, gem_kind = len(gems), len(set(gems))
    gems_dict = defaultdict(lambda: 0)
    
    while True:
        kind = len(gems_dict)
        if start == gems_len:
            break
        if kind == gem_kind:
            candidates.append((start, end))
            gems_dict[gems[start]] -= 1
            if gems_dict[gems[start]] == 0:
                del gems_dict[gems[start]]
            start += 1
            continue
        if end == gems_len:
            break
        if kind != gem_kind:
            gems_dict[gems[end]] += 1
            end += 1
            continue

    length = float('inf')
    for s, e in candidates:
        if length > e-s:
            length = e-s
            answer[0] = s + 1
            answer[1] = e
    return answer

• 계속 시간초과가 나와서 참고했던 코드다

https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B3%B4%EC%84%9D%EC%87%BC%ED%95%91-a901de0ce34

[프로그래머스] 보석쇼핑

 

기억해야할 것

• 시간초과의 원인
  • 보유해야할 종류의 보석의 개수 중 0이 있는지 확인하도록 만들었다
    - 매 loop마다 보석 종류 개수만큼 탐색하여 시간초과
  • dict의 0을 제거하기위해 Counter()를 더했다
    - "파이썬 알고리즘 인터뷰"에서 보았던 편법(?)인데 시간초과를 초래했다