Py) 프로그래머스 67258 보석 쇼핑

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

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

 

1차: 1시간 2분

2차: 24분

 

0. 입출력

 

1. 내 접근

1)  진열된 보석의 종류를 파악한다.(gem_list) gems 리스트에 범위를 지정하고, 범위만큼 리스트 처음~끝까지 보석 종류가 전부 있는지 확인한다. 없다면 범위를 하나씩 키워줘서 반복

-> 시간초과 뜸

다 통과하는데 11, 14번에서 시간초과 뜸

2) gem_list에서 원소를 하나씩 start point로 지정하고 각 start point를 범위의 시작점으로 설정하고 찾아주면 조금 시간을 줄일 수 있지 않을까?

-> 테스트케이스 3번의 경우에서 틀림

 

1.2 내 코드 -> 시간초과

def solution(gems):
    answer = [1, len(gems)]
    gem_list = set(gems)
    gem_size = len(gem_list)

    size = 0
    while size < len(gems)-gem_size:
        for i in range(0, len(gems)-gem_size+1):
            if set(gems[i:gem_size+i+size]) == gem_list:
                answer = [i+1, gem_size+i+size]
                return answer

        size += 1


    return answer

 

2. Solution

2.1 알고리즘: 이진탐색

2.2 로직

1) 보석의 종류 리스트(gem_list), 범위에 포함되어 있는 보석 리스트(gem_range)를 만든다. (dictionary 사용)
범위에 포함되어 있는 리스트의 크기가 보석 종류 리스트의 크기와 동일해야한다.

2) len(gem_list) > len(gem_range)    # 아직 모든 보석이 범위에 다 들어오지 않았을때
right 인덱스의 크기를 늘려 범위를 키우고, 키운 범위에 있는 보석을 dic에 포함해 key값을 늘려 개수를 표현해준다.

3) len(gem_list) == len(gem_range)    # 모든 보석이 범위에 들어옴
튜플의 형태로 해당 범위를 answer에 포함시켜주고,
중복된 보석이 있을 수 있으므로, left를 줄여준다.

4) len(gem_list)<len(gem_range)    # 이런 경우는 없을거 같은데.. 범위에 들어온 보석이 종류 리스트보다 크다면
left 인덱스를 줄여준다. 이때 left인덱스에 해당하는 보석의 개수가 0이면 하나씩 지워줌

2.3 코드

def solution(gems):
    answer = []
    gem_list = set(gems)    # 보석 종류
    gem_size = len(gem_list)

    gem_range = dict()      # 보석을 사야하는 범위
    gem_range[gems[0]] = 1

    left = 0
    right = 1
    while left < right:
        if gem_size == len(gem_range):
            answer.append((right-left, left, right))

            if gem_range[gems[left]] > 0:
                gem_range[gems[left]] -= 1
            if gem_range[gems[left]] == 0:
                del(gem_range[gems[left]])
            left += 1

        elif gem_size > len(gem_range):
            if right < len(gems):
                gem_range[gems[right]] = gem_range.get(gems[right], 0)+1
                right += 1
            else:       # right >= len(gems)
                break
        else:       # gem_size < len(gem_range)
            if gem_range[left] > 0:
                gem_range[left] -= 1
            elif gem_range[left] == 0:
                del(gem_range[left])
            left += 1

    answer.sort()
    return [answer[0][1]+1, answer[0][2]]

print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))

ref - https://yanoo.tistory.com/85사랑합니다..

 

3. 피드백

이진탐색은 정말 의외였다. 흥미돋.

dict()를 사용해서 중복과 범위 포함을 동시에 체크해주는 생각이 좋았던거 같음

 

4. 새롭게 알게된 것들

gem_range[gems[right]] = gem_range.get(gems[right], 0)+1

에서, dic.get(dic2[key], 0) -> dic2에 해당 키값이 있으면 value를 반환하지만, 없으면 0을 반환.