[카카오 인턴] 보석 쇼핑 (lv3)

문제

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

풀이

본 문제는 투포인터 알고리즘을 이용하여 해결 가능하다. 이번 문제를 통해 해당 알고리즘의 존재를 처음 알았다.

[Algorithm] 투포인터(Two Pointer) 알고리즘 (tistory.com)

[Algorithm] 투포인터(Two Pointer) 알고리즘

담은 보석의 종류가 기대치에 못미친다면 오른쪽 포인터를 움직여 보석을 담고, 만약 충분하거나 기대치 이상이라면 왼쪽 포인터를 움직여 보석을 다시 내놓는다. 문제에서는 기대치를 만족하는 경우 중 보석의 총 개수가 가장 적고, 또한 가장 적은 개수를 담는 경우가 여러개 있을 경우 왼쪽 포인터가 최대한 왼쪽을 가리키는 경우를 원하고 있다. 따라서 현재 보석의 총 개수보다 작을때만 answer를 갱신하도록 하면 된다. 본 문제에서는 효율성 테스트 또한 존재하므로, 매번 포인터들을 움직일 때 마다 보석의 종류를 파악하는 방법보다는, 보석의 종류별로 현재 시점의 개수를 계속해서 갱신해가는 편이 좋다. 카카오의 고난이도 문제다운, 발상이 중요한 문제가 되겠다.

def solution(gems):
    answer = []
    s = set(gems)
    length = len(gems)
    limit = len(s)
    i,j = 0,limit-1
    dic = dict()
    cnt = 0
    for k in range(i,j+1):
        if not dic.get(gems[k]):
            dic[gems[k]] = 0
            cnt += 1
        dic[gems[k]] += 1
    while i < length and j < length:
        if cnt >= limit:
            if not answer or j-i < answer[1]-answer[0]:
                answer = [i+1,j+1]
            dic[gems[i]] -= 1
            if dic[gems[i]] == 0:
                cnt -= 1
            i += 1
        else:
            j += 1
            if j < length:
                if not dic.get(gems[j]):
                    dic[gems[j]] = 0
                if dic[gems[j]] == 0:
                    cnt += 1
                dic[gems[j]] += 1
    return answer