프로그래머스 2020 카카오 인턴십 투 포인터 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (정확성 테스트 15/15 성공, 효율성 테스트 2/15 성공)

def solution(gems):
    answer = [-1,-1,len(gems)+1]
    
    kinds = len(set(gems))
    
    start = 0
    end = 0
    
    while end <= len(gems)+1:
        
        buy = len(set(gems[start:end+1]))
                
        if buy==kinds:
            now_len = end-start+1 
            if now_len<answer[2]:
                answer = [start+1,end+1,now_len]
                if now_len==kinds:
                    break
            start += 1
            
        elif buy<kinds:
            end += 1
            
    answer = answer[:2]
    
    return answer

보석들의 배열(gems)이 주어지고 연속된 구간의 보석들을 구매해야하며 모든 종류의 보석들을 구매하기 위한 최소 길이를 찾는 문제입니다.🐐🐐🐐

투 포인터 알고리즘을 활용해야하는 것을 직감하고 start, end 각 포인터를 0으로 초기화하며 진행하였습니다.

보석 배열을 start~end 구간으로 슬라이싱해가며 현재 구간까지 종류가 적으면 end값을 늘리고 종류가 많다면 start값을 줄이는 방식으로 최소값을 도출하였고 정확성 테스트까지는 전부 맞출 수 있었습니다.

하지만 효율성 테스트에서 대부분 시간 초과가 발생하여 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(gems):
    N = len(gems)
    answer = [0, N-1]
    kind = len(set(gems))  # 보석종류
    dic = {gems[0]:1,}  # 종류 체크할 딕셔너리
    s,e = 0,0  # 투포인터
    while s<N and e<N:
        if len(dic) < kind:  # 종류 부족하면 end point 증가 & dic 개수 증가
            e += 1
            if e == N:
                break
            dic[gems[e]] = dic.get(gems[e], 0) + 1
            
        else:  # 종류 같으면 ans 비교 후 답 갱신하고, start point 증가 & dic 개수 다운
            if (e-s+1) < (answer[1]-answer[0]+1):
                answer = [s,e]
            if dic[gems[s]] == 1:
                del dic[gems[s]]
            else:
                dic[gems[s]] -= 1
            s += 1

    answer[0] += 1
    answer[1] += 1
    return answer

'나의 풀이'에서 현재 start~end의 n구간을 슬라이싱하여 종류별 갯수를 파악하는 방법이 시간복잡도 O(n)를 발생시키므로 dict로 현황을 파악하여 해결한 풀이였습니다.🐓🐓🐓

dict 객체에 보석종류별 갯수를 표현하여 판별하는 방식입니다. 만약 종류별 갯수가 크다면 gems[start]에 해당하는 value 값을 줄이고 , 작다면 gems[end]에 해당하는 value를 하나씩 추가해주는 알고리즘이였습니다.

[다른 사람의 풀이2]

def solution(gems):
    answer = [0, 0]
    candidates = []
    start, end = 0, 0
    gems_len, gem_kind = len(gems), len(set(gems))
    gems_dict = defaultdict(lambda: 0)
    
    while True:
        kind = len(gems_dict)
        if start == gems_len:
            break
        if kind == gem_kind:
            candidates.append((start, end))
            gems_dict[gems[start]] -= 1
            if gems_dict[gems[start]] == 0:
                del gems_dict[gems[start]]
            start += 1
            continue
        if end == gems_len:
            break
        if kind != gem_kind:
            gems_dict[gems[end]] += 1
            end += 1
            continue

    length = float('inf')
    for s, e in candidates:
        if length > e-s:
            length = e-s
            answer[0] = s + 1
            answer[1] = e
    return answer

'다른 사람의 풀이1'과 같이 투 포인터 & dict객체를 활용한 풀이입니다. 약간 다른점으로 현재 구간의 보석 종류별 갯수를 파악할 때

gems_dict = defaultdict(lambda: 0)

위 defaultdict() 객체를 활용하여 존재하지 않는 key,value를 호출하여도 defalut값을 0으로 출력하게 하여 코드를 간결히 표현했다는 점입니다.

감사합니다.🐢🐢🐢