[Seop's의 코드풀이] 프로그래머스 보석쇼핑 - Python

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

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

 

 

문제요약

배열에 있는 문자열의 종류를 모두 포함하는 최소 구간을 찾으면 되는 문제입니다. 

간단하게 모든 경우의 수를 생각하면서 문제를 풀게되면 시간초과가 나게됩니다. 

 

문제풀이 IDEA

시간 초과 없이 문제를 해결하기 위해 다음과 같은 고민을 진행하였습니다.

• 배열에 있는 문자열을 한번만 순환하여 찾는 방법이 없을까?
• 특정 구간 안에 있는 문자열의 종류의 수를 한번에 찾을 수 없을까?

먼저 한번만 순환하여 찾는 방법으로

지렁이 처럼 펴졌다 줄여들면서 탐색을 진행하는 방식을 선택했습니다.

좀 더 쉬운 이해를 위해 다음 그림을 참조하면 좋을 것 같습니다.  

노란색 구간이 현재 구간입니다. 

만약 현재 구간안에 있는 문자열의 종류의 수가 전체 문자열의 종류의 수보다 작다면 j(빨간)값을 증가 시키면서 탐색을 진행합니다.  

문자열 종류의 수가 같다면 i(파란)값을 증가시키고 정답 후보에 저장합니다. 

 

이러한 방법으로 탐색을 진행한다면 최대 2N 번만에 모든 경우를 파악 할 수 있습니다. 

특정 구간안에 있는 문자열 종류의 수를 한번에 체크 하기위해서 다음과 같은 알고리즘을 통해서 이루어졌습니다.

• myGems(딕셔너리)
  Key : 문자열 
  Value : 문자열이 나온 횟수
• g_len : 전체 문자열 종류의 수
• m_len : 특정 구간의 문자열 종류의 수 
• i : 꼬리를 가리키는 Index
• j : 머리를 가리키는 Index

만약 m_len 과 g_len의 값이 다르다면?

- j 가 가리키는 문자열이 딕셔너리에 있다면 해당 값을 1 증가 시키고 없다면 m_len 의 길이를 1 증가 시키고 딕셔너리에 값을 입력한다.

- j 값을 1 증가시킨다.

만약 m_len 과 g_len의 값이 같다면?

- 정답 구간 후보에 i, j 값을 추가한다.

- 딕셔너리에서 i 가 가리키는 문자열에 해당하는 Value 값을 1 감소시킨다.

- Value 값이 0 이된다면 딕셔너리에서 제거하고 m_len 값을 1 감소시킨다.

- i 값을 1 증가시킨다.

이러한 과정을 j 값이 끝까지 다을때 까지 지속한다. 

 

전체코드 

def solution(gems):
    answer = []

    setGems = set(gems)
    g_len = len(setGems)
    myGems = dict()
    m_len = 0

    i = 0
    j = 0
    flag = True     #구간을 줄일지 늘릴지 결정하는 Flag

    while j < len(gems) or not flag :
        # 구간이 줄어든다면 j가 끝까지 갔어도 계속 진행
        if flag :
            if gems[j] not in myGems :
                myGems[gems[j]] = 1
                m_len += 1
            else :
                myGems[gems[j]] += 1
            j += 1
        else :
            myGems[gems[i]] -= 1
            if myGems[gems[i]] == 0 :
                myGems.pop(gems[i])
                m_len -= 1
            i += 1

        if m_len == g_len :
            flag = False
            answer.append([i+1,j])
        else :
            flag = True

    # 정답 후보에서 그 차이가 가장 작은 값을 중심으로 정렬
    result = sorted(answer, key= lambda x: ((x[1]-x[0]), x[0])   )
    return result[0]

 

질문과 피드백은 언제나 감사드립니다.