[프로그래머스] 보석 쇼핑 / python 파이썬 / 2020 카카오 인턴십 코테

 

🐥 2020 카카오 인턴십

 

문제

 

thinking

완전탐색으로 풀면 시간복잡도 O(N²) 여서 안됨. ->  투포인터  로 풀자

1. 실패코드

처음에 리스트 슬라이싱과 set을 이용해 풀었는데 효율성이 똥망이었다.... 왜???????????????? 투포인터로 풀었는데 😲

def solution(gems):
    N = len(gems)
    answer = [0, N-1]
    kind = set(gems)
    s,e = 0,0  # 투포인터
    while 0<=s<N and 0<=e<N:
        if set(gems[s:e+1]) == kind:  # 모든 종류 다 갖고 있으면 start point 증가시키면서 최소구간 구하기
            if (e-s+1) < (answer[1]-answer[0]+1):
                answer = [s,e]
            s += 1
        else:  # 종류 부족하면 end point 증가시키기
            e += 1
    answer[0] += 1
    answer[1] += 1
    return answer

왜냐하면 리스트 슬라이싱으로 풀었기 때문이다. 슬라이싱은 객체 k개를 조회해야하므로 시간복잡도가 O(k)이다. 거의 뭐 완탐하는 수준 ;;; 그래서 결론은 슬라이싱을 버려라 !!!!!!!!!

 

2. 맞은코드

카카오 테크 블로그 해설을 보니  딕셔너리 로 풀라길래 재도전해봤다

카카오 공식 해설

 

코드

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