보석 쇼핑 - 2020 카카오 인턴십 문제 (python, javascript)

프로그래머스, 2020 카카오 인턴십 코딩테스트 기출 - 보석 쇼핑 LV3

https://programmers.co.kr/learn/courses/30/lessons/67258
효율성 뚫기가 쉽지 않았던 문제 "양끝 포인터 사용"

👀 깃헙 소스

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

입출력 예
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]"=====>>> [3, 7]

예시 설명
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

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

코드

# 파이썬
def solution(gems):

    TYPE_NUM = len(set(gems))
    GEM_NUM = len(gems)
    cur_shop = {gems[0]: 1}
    cand = []
    l_idx, r_idx = 0, 0
    DIST, RESULT = 0, 1

    while l_idx < GEM_NUM and r_idx < GEM_NUM:
        if len(cur_shop) < TYPE_NUM:
            r_idx += 1
            if r_idx == GEM_NUM:
                break
            cur_shop[gems[r_idx]] = cur_shop.get(gems[r_idx], 0) + 1
        else:
            cand.append((r_idx-l_idx, [l_idx+1, r_idx+1]))
            cur_shop[gems[l_idx]] -= 1
            if cur_shop[gems[l_idx]] == 0:
                del cur_shop[gems[l_idx]]
            l_idx += 1

    cand = sorted(cand, key=lambda x: (x[DIST], x[RESULT]))

    return cand[0][RESULT]

// 자바스크립트
function solution(gems) {
    const gemTypeNum = new Set(gems).size
    const gemsNum = gems.length
    let gemMap = new Map();
    gemMap.set(gems[0], 1)
    let left = 0,
        right = 0
    let cand = []

    while (left < gemsNum && right < gemsNum) {
        if (gemMap.size < gemTypeNum) {
            right++;
            gemMap.set(gems[right], (gemMap.get(gems[right]) || 0) + 1)
        } else {
            cand.push([left + 1, right + 1])
            gemMap.set(gems[left], gemMap.get(gems[left]) - 1)
            if (gemMap.get(gems[left]) === 0) gemMap.delete(gems[left])
            left++;
        }
    }
    cand.sort((a, b) => {
        return a[1] - a[0] === b[1] - b[0] ? a[0] - b[0] : (a[1] - a[0]) - (b[1] - b[0])
    })
    return cand[0]
}

효율성 실패 코드

큐사용 - python

from collections import deque, defaultdict

def solution(gems):

    gem_set = set(gems)
    LEN = len(gem_set)
    get_set = set()
    get_dict = defaultdict(int)
    sidx, eidx = 1, 0
    que = deque(gems)
    get_que = deque([])
    cand = []
    min_len = 999999
    flag = False

    while que:
        item = que.popleft()
        get_que.append(item)
        get_set.add(item)
        get_dict[item] += 1
        eidx += 1
        while get_que and get_dict[get_que[0]] > 1:
            get_dict[get_que.popleft()] -= 1
            sidx += 1

        if flag or gem_set & get_set == gem_set:
            if min_len > eidx - sidx:
                cand = [sidx, eidx]
                min_len = eidx - sidx
                if min_len == LEN-1:
                    return cand
                if not flag:
                    flag = True
    return cand

key 값을 지우지 않았을 때 - python

def solution(gems):
    UNIQUE_GEM = set(gems)
    TYPE_NUM = len(UNIQUE_GEM)
    GEM_NUM = len(gems)
    cur_shop = { gem : 0 for gem in UNIQUE_GEM }
    cand = []
    l_idx, r_idx = 0, 0
    
    cur_shop[gems[0]] += 1 
    while l_idx < GEM_NUM and r_idx < GEM_NUM:
        if 0 in cur_shop.values(): # 이 부분이 오래걸림
            r_idx += 1
            if r_idx == GEM_NUM:
                break;
            cur_shop[gems[r_idx]] += 1
        else:
            cand.append((r_idx-l_idx, [l_idx+1, r_idx+1]))
            cur_shop[gems[l_idx]] -= 1
            l_idx += 1

    cand = sorted(cand, key = lambda x: (x[0], x[1]))

    return cand[0][1]

Map을 사용하지 않고 object를 사용했을 때 - js

ES6부터 등장한 Map을 사용하여 효율성 증가 가능,
*참고 Map vs Object : https://medium.com/front-end-weekly/es6-map-vs-object-what-and-when-b80621932373

function solution(gems) {
    const gemTypeNum = [...new Set(gems)].length
    const gemsNum = gems.length
    let gemMap = {
        [gems[0]]: 1
    };
    let left = 0,
        right = 0
    let cand = []

    while (left < gemsNum && right < gemsNum) {
        if (Object.keys(gemMap).length < gemTypeNum) {
            right++;
            if (right === gemsNum) break;
            gemMap[gems[right]] = (gemMap[gems[right]] || 0) + 1
        } else {
            cand.push([left + 1, right + 1])
            gemMap[gems[left]]--;
            if (gemMap[gems[left]] === 0) delete gemMap[gems[left]]
            left++;
        }
    }
    cand.sort((a, b) => {
        return a[1] - a[0] === b[1] - b[0] ? a[0] - b[0] : (a[1] - a[0]) - (b[1] - b[0])
    })
    return cand[0]
}