Level 3 보석 쇼핑 <2020 카카오 인턴십> Python 3

https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3 

코딩테스트 연습 - 보석 쇼핑

 

최종 코드

• https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_보석%20쇼핑.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(gems):
    kinds = len(set(gems))
    g_dict = dict()
    answer = []
    start = 0
    end = 0
    differ = len(gems)
    while end < len(gems):
        if gems[end] not in g_dict:
            g_dict[gems[end]] = 1
        else:
            g_dict[gems[end]] += 1
        if len(g_dict) == kinds:
            while start <= end:
                if g_dict[gems[start]] - 1 > 0:
                    g_dict[gems[start]] -= 1
                    start += 1
                elif end - start < differ:
                    answer = [start, end]
                    differ = end-start
                    break
                else: break
        end += 1
                
    return [answer[0]+1, answer[1]+1]

---

풀이 과정

def solution(gems):
	#보석 종류 개수
    kinds = len(set(gems))
    #start~end까지의 보석 개수 카운팅
    g_dict = dict()
    
    answer = []
    start = 0
    end = 0
    #differ = end-start
    differ = len(gems)
    while end < len(gems):
    	#end번째 보석 종류가 g_dict에 없는 보석인 경우, 추가한다
        if gems[end] not in g_dict:
            g_dict[gems[end]] = 1
        #end번쨰 보석 종류가 g_dict에 이미 있는 보석인 경우, 카운팅
        else:
            g_dict[gems[end]] += 1
        #start~end까지 모든 종류의 보석이 g_dict에 있다면, 더 짧은 구간을 찾는다
        if len(g_dict) == kinds:
        	#start값을 1씩 증가하면서 모든 종류의 보석을 가질 수 있는 더 짧은 구간을 찾는다
            while start <= end:
            	#start에 있는 보석을 제외해도 모든 종류의 보석을 가질 수 있다면, 다음 인덱스부터 보석을 사도 된다
                if g_dict[gems[start]] - 1 > 0:
                    g_dict[gems[start]] -= 1
                    start += 1
                #start에 있는 보석을 포함해야하고, 현재 구간이 differ보다 짧으면 answer과 differ을 갱신하고 break
                elif end - start < differ:
                    answer = [start, end]
                    differ = end-start
                    break
                #start에 있는 보석을 포함해야하고, 현재 구간이 differ보다 짧지 않으면 가장 짧은 구간이 아니므로 break
                else: break
        end += 1
                
    return [answer[0]+1, answer[1]+1]
#시간복잡도 = O(n^2), 공간복잡도 = O(n)

---

오답 노트

 모든 경우의 수로 가장 짧은 구간을 구하려고 했다. len(gems)의 길이가 최대 100,000으로 주어지기 때문에 이 경우 정확성은 다 맞았지만 효율성에서 시간초과로 통과하지 못했다. 투포인터 문제를 더 연습해야 할 것 같다

def solution(gems):
    answer = []
    kinds = len(set(gems))
    start = 0
    end = len(gems)-1
    set_g = set()
    for i in range(0, len(gems)):
        set_g.clear()
        for j in range(i, len(gems)):
            set_g.add(gems[j])
            if len(set_g) == kinds and end-start > j-i:
                start = i
                end = j
                break
    return [start+1, end+1]

---

참고

• 1. 키패드 누르기 -> https://hwayomingdlog.tistory.com/138

Level 1 키패드 누르기 <2020 카카오 인턴십> Python 3

• 2. 수식 최대화
• 4. 경주로 건설
• 5. 동굴 탐험