프로그래머스 :: 보석 쇼핑 (Python)

문제 링크

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

프로그래머스

 

접근 방식

문제에서 주어진 보석 배열을 완전 탐색해야하는 문제이다.

그런데 N 이 10만..? 일반적인 탐색 알고리즘은 O(N^2) 이기 때문에,

O(N) 인 투포인터를 써야 하나 생각했다.

여기서 left, right 두 포인터를 인덱스로 두고 그 사이에 어떤 보석들이 있는지를 확인해야 하는데,

이 부분에서 효율성 점수가 깎일 수 있다.

어차피 포인터를 하나씩 증가시키기 때문에 gem_dict 라는 딕셔너리를 하나 만들어서

left 포인터가 한칸 증가하면 이전 dict 값은 하나 줄이고,

right 포인터가 한칸 증가하면 증가한 인덱스의 dict 값은 증가시키는 방식으로 구현했다.

 

풀이 코드

def solution(gems):
    answer = [1, len(gems)]
    gem_dict = {gems[0]: 1}
    kind = set(gems)
    len_range = 1e9

    left, right = 0, 0
    while left <= right and right < len(gems):
        if len(kind) == len(gem_dict):
            if (right - left) < len_range:
                len_range = right - left
                answer = [left+1, right+1]
            gem_dict[gems[left]] -= 1
            if gem_dict[gems[left]] == 0:
                del gem_dict[gems[left]]
            left += 1
        else:
            right += 1
            if right >= len(gems):
                break
            gem_dict[gems[right]] = gem_dict.get(gems[right], 0)
            gem_dict[gems[right]] += 1

    return answer

끝.