[프로그래머스] 보석 쇼핑 (파이썬)

문제

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

문제 설명

제한사항

gems 배열의 크기는 1 이상 100,000 이하입니다.
gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

🧭 접근

처음에는 시작점과 끝점을 배열의 처음부터 끝까지 지정한 후, 가장 짧은 구간이 나올때 까지 양 쪽을 줄이며 카운트하여 답을 찾으려고 했다. 하지만 효율성 테스트에서 실패 하였다. 그래서 직접 함수를 작성하여 모든 보석이 포함되었는지 확인 했었는데, 이 부분은 Counter 함수를 사용하였고, 탐색은 투 포인터 알고리즘을 활용하고, 또한 최대한 카운트를 줄이고자 했다.

✔ 풀이

1. 입력으로 들어온 문자열을 처리하여 숫자와 연산자를 분리하여 배열에 저장
2. 연산자에 우선순위를 두기 위해 연산자의 조합을 만들기
3. 만들어진 연산자 조합의 우선순위에 따라 계산
4. 3을 반복하며 식의 계산 결과값을 저장
5. 가장 큰 값 return

📙 소스 코드

from collections import Counter

def solution(gems):
    gem_ctr = Counter(gems) # gems Counter
    ctr_len = len(gem_ctr) #보석 종류 갯수 
    gems_len = len(gems) # gems 배열의 길이
    res = [1,gems_len] # 최대값으로 초기화
    
    st = 0 # 시작지점
    ctr = Counter()
    for ed in range(gems_len): # 끝지점
        ctr[gems[ed]] +=1 # ed에 해당하는 보석의 갯수 갱신

		# st에 해당하는 보석의 갯수가 1보다 크다면, 필요없으므로 st 증가 및 보석 개수 감소 시키기
        while ctr[gems[st]] > 1: 
            ctr[gems[st]] -= 1
            st +=1
            
        if len(ctr) == ctr_len: # 모든 종류가 있을경우
            if abs(st-ed) == ctr_len-1: # 최소 길이(종류의 갯수)가 나오면 더 계산할 필요가 없음
                res = [st+1,ed+1]
                break 
            prev = abs(res[0] - res[1]) # 이전 값과 비교하여 길이가 짧거나 인덱스가 앞쪽이면 res 갱신
            if prev > abs(st-ed):
                res = [st+1,ed+1]
            elif prev == abs(st-ed):
                if res[0] > st:
                    res = [st+1,ed+1]

    return res

🤔 느낀 점

푸는데 매우 오래 걸렸다. 레벨 3 문제 부터는 적합한 알고리즘을 찾아 문제에 적용하여 풀어야 하기 때문에, 코딩테스트에 필요한 알고리즘들을 최대한 반복 숙달 해야겠다고 느꼈다.