프로그래머스 Lv. 3 보석 쇼핑 Python

문제 링크

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

프로그래머스

정답 코드

def solution(gems):
    type_count = len(set(gems))  # 보석의 종류 수
    left, right = 0, 0
    lenGems = len(gems)
    answer = [0, lenGems - 1]
    gem_map = dict()  # 현재 윈도우에 있는 보석의 종류와 수를 저장

    while right < lenGems:
        # 윈도우를 오른쪽으로 확장
        if gems[right] not in gem_map:
            gem_map[gems[right]] = 0
        gem_map[gems[right]] += 1
        
        # 윈도우에서 모든 종류의 보석을 포함하는 경우
        while len(gem_map) == type_count:
            # 더 작은 길이를 찾으면 업데이트
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
            
            # 윈도우를 왼쪽으로 축소
            gem_map[gems[left]] -= 1
            if gem_map[gems[left]] == 0:
                del gem_map[gems[left]]
            left += 1

        right += 1
    
    # 인덱스는 1부터 시작하므로 1을 추가
    return [answer[0] + 1, answer[1] + 1]

풀이 방법

- 처음 이거를 for문으로 만드려고 했는데 문제는 100,000개 배열을 2중 반복하면 시간초과가 발생

- 왼쪽부터 탐색 시작

- 왼쪽 처음 보석부터 dictionary에 하나씩 넣으면서 길이를 확인

- 길이가 보석의 종류 갯수와 똑같으면 현재 범위에서 왼쪽을 줄여가며 최소 길이 확인

    - 여기서 갑자기 보석의 종류 갯수가 하나라도 줄어들면 종료

- 이 알고리즘은 각 요소를 한 번씩만 검사하므로 시간 복잡도는 O(N)이다.

느낀점

- for문으로 이중 반복문 했을 때는 확실히 모든 index를 set()에 add를 시켜서 시간초과가 난 것 같다.

- 다음에 꼭 다시 풀어야 하며 딕셔너리 지우는 del 이거 외워야 겠다.

 

Key Point

Python의 del 함수는 객체를 삭제하는 데 사용됩니다. 이는 변수, 리스트의 요소, 사전의 키 등 다양한 객체와 구조에서 특정 요소를 제거하는 데 사용될 수 있습니다. del은 메모리에서 객체를 제거하는 것이 아니라, 이름과 해당 객체 간의 연결을 끊는 것입니다. 객체에 대한 모든 참조가 제거되면, Python의 가비지 컬렉터가 나중에 메모리에서 해당 객체를 제거합니다.

del의 사용 예시:

• 변수 삭제:

x = 10 
del x # 이제 x는 더 이상 존재하지 않습니다.

• 리스트 요소 삭제:

numbers = [1, 2, 3, 4, 5]
del numbers[2]  # 이제 numbers는 [1, 2, 4, 5]가 됩니다.

• 사전 키 및 해당 값 삭제:

data = {'a': 1, 'b': 2, 'c': 3}
del data['b']  # 이제 data는 {'a': 1, 'c': 3}가 됩니다.

• 슬라이싱을 이용한 부분 삭제:

a = list(range(10))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
del a[::2]  # 인덱스가 짝수인 요소를 모두 삭제합니다. 결과: [1, 3, 5, 7, 9]