프로그래머스 : 보석 쇼핑 - 파이썬

rn/courses/30/lessons/67258

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

 

배열의 크기가 10만 이하이므로 시간 복잡도를 고려하여 풀어야하는 문제라고한다. 시간 복잡도를 잘몰라서 무작정 구현(?) 하려고 했는데 여러 풀이들을 찾아보니  슬라이딩 윈도우(투 포인터) 알고리즘을 사용한다고 한다 근데 아직 잘모르겠다...ㅠㅠ

1. 초기값 설정

start, end 인덱스 모두 인덱스 0에서 시작하는 것으로 세팅한다.
dic[gems[start]] +=1 , 즉 dic['DIA']에 +1을 해준다. 이 때, 처음 갖는 보석이므로 check_num += 1 하여 가지고 있는 보석의 종류를 관리하였다.

2. 가지고 있는 보석의 종류가 충족되지 않는 경우

end 포인터를 1씩 늘려가며 가지고 있는 보석의 종류를 체크한다.

3. 가지고 있는 보석의 종류가 충족된 경우

start인덱스와 end 인덱스 사이 구간 값을 확인 -> 더 짧은 구간인 경우 갱신 -> start 포인터 1씩 늘리며 확인을 반복한다.

"가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다." 라는 조건이 있으므로, 순서대로 확인하되 짧은 구간일 경우 갱신해주면 된다.

문제 코드

def set_dic(gems):
    result = {}
    for gem in gems:
        result[gem] = 0
    return result

def solution(gems):
    answer = []
    min_val = 100000
    dic = set_dic(gems)    
    #초기값 설정
    start, end = 0, 0
    dic[gems[start]] += 1
    check_num = 1
    while True:
        if check_num == len(dic):
            if min_val > end-start:
                min_val = end-start
                answer = [start+1, end+1]
            #start 포인터 값 제외
            dic[gems[start]] -= 1
            if dic[gems[start]] == 0:
                check_num -= 1
            #start 포인터 한 칸 앞으로
            start += 1
            if start >= len(gems):
                break
        else:
            #end 포인터 한 칸 앞으로
            end += 1
            if end >= len(gems):
                break
            #end 포인터 값 추가
            dic[gems[end]] += 1
            if dic[gems[end]] == 1:
                check_num += 1
    return answer