[2020 카카오 인턴십] 보석 쇼핑

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

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

 

효율성 테스트를 통과 못해서 애먹었다.

 

1. 처음에 짰던 코드, 당연히 효율성에서 다 틀렸다.

def solution(gems):
    answer = [0, 100000]
    glist = []
    for i in gems:
        if i not in glist:
            glist.append(i)
    
    case = []
    for i in range(len(gems)):
        glist2 = []
        for j in range(i, len(gems)):
            if gems[j] not in glist2:
                glist2.append(gems[j])
            if len(glist2) == len(glist):
                case.append([i+1, j+1])
                break
    for i in case:
        if i[1]-i[0] < answer[1]-answer[0]:
            answer = [i[0], i[1]]
    return answer

 

 

2. 딕셔너리쓰고 하니까, 그래도 효율성 몇개 빼곤 통과했다.

def solution(gems):
    answer = [1, 100000]
    count = len(set(gems))
    a = {}
    for i in range(len(gems)):
        a[gems[i]] = i
        m1 = i
        m2 = min(a.values())
        if len(a) == count:
            if m1-m2 < answer[1]-answer[0]:
                answer = [m2+1, m1+1]
    return answer

 

 

3. min()과정이 효율성을 좀 잡아먹는 것 같아서, 수정... 근데도 계속 통과를 못했다.

def solution(gems):
    answer = [1, 100000]
    count = len(set(gems))
    a = {}
    for i in range(len(gems)):
        if gems[i] in a:
            del a[gems[i]]
        a[gems[i]] = i
        m1 = i
        m2 = list(a.values())[0]
        if len(a) == count:
            if m1-m2 < answer[1]-answer[0]:
                answer = [m2+1, m1+1]
    return answer

 

4. m1, m2정리했더니, 통과.?...?

def solution(gems):
    answer = [1, 100000]
    count = len(set(gems))
    a = {}
    for i in range(len(gems)):
        if gems[i] in a:
            del a[gems[i]]
        a[gems[i]] = i
        if len(a) == count:
            if i-list(a.values())[0] < answer[1]-answer[0]:
                answer = [list(a.values())[0]+1, i+1]
    return answer

 

 

 

아무튼, 모든 보석을 1개 이상 포함하면서 가장 짧은 구간을 찾아 반환해주면된다.

 

1. count = len(set(gems)) , set함수를 통해 보석의 종류 수를 구한다.

2. 딕셔너리 a를 선언, 딕셔너리 a의 키는 보석이름, 값은 보석이 있는 인덱스이다.

3. 리스트 gems를 돌면서, 딕셔너리 a에 보석을 추가한다.

  - 만약 이미 추가된 보석이라면, 딕셔너리에서 삭제한뒤 추가한다.

  - update를 하거나 그냥 덮어씌워도 가능하지만, 삭제한뒤 추가하는 이유는, 딕셔너리에 데이터가 삽입된 순서대로 위치하기 때문이다.

  (Python 3.7 버전부터라고 한다.)

4. 만약 길이가 count와 같으면(모든 보석을 1개 이상 포함하면), a딕셔너리의 양 끝 값의 차(구간의 길이)를 anwer구간의 길이와 비교해,

answer보다 짧다면 answer을 교체해준다.

 

(구간) = (딕셔너리의 맨앞의 값+1) ~ i+1                        #진열대 번호는 1부터 시작하므로 +1

 

딕셔너리의 값 변화 과정