[프로그래머스]67258 : 보석 쇼핑 | 투포인트 탐색

[프로그래머스] 67258 : 보석 쇼핑

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

프로그래머스

 

---

[python] 문제 풀이

 

• 모든 보석 종류를 최소한 하나씩 포함하는 구간을 찾아야 함
• 투 포인터를 활용해 구간을 효율적으로 줄여나감
• 딕셔너리를 사용해 현재 구간에 포함된 보석의 개수를 관리

 

while end < len(gems):
    # end 포인터를 이동시키며 보석 추가
    if gems[end] in gem_count: 
        gem_count[gems[end]] += 1
    else:
        gem_count[gems[end]] = 1
    end += 1

• while end < len(gems): end 포인터가 배열의 끝에 도달할 때까지 반복
• if gems[end] in gem_count: 현재 end 포인터가 가리키는 보석이 gem_count에 이미 있는지 확인
  • 있으면: 그 보석의 개수 +1
    ex) 현재 gem_count에 DIA: 2가 있고, gems[end]가 DIA라면, gem_count = {"DIA": 3}
  • 없으면: 현재 구간에 처음으로 추가되는 것 -> 현재 구간에 이 보석의 개수를 1로 초기화
    ex)  gem_count가 빈 딕셔너리인 경우, gems[end]가 DIA라면, gem_count =  {"DIA": 1}
• end += 1: end 포인터를 오른쪽으로 이동

 

while len(gem_count) == total_gems:
    # 현재 구간이 더 짧은 경우 갱신
    if end - start - 1 < result[1] - result[0]:
        result = [start, end - 1]

• while len(gem_count) == total_gems: 현재 구간에 포함된 보석 종류의 수가 전체 보석 종류와 같을 때까지 반복
• if end - start - 1 < result[1] - result[0]: 현재 구간의 길이(end - start - 1)가 기록된 최소 구간의 길이보다 짧으면 result를 업데이트
• result - > 가장 짧은 구간의 시작과 끝 인덱스 저장 

 

 gem_count[gems[start]] -= 1
    if gem_count[gems[start]] == 0:
        del gem_count[gems[start]]  # 개수가 0이 되면 해당 보석 제거
    start += 1

• gem_count[gems[start]] -= 1: start 포인터가 가리키는 보석의 개수 -1
• if gem_count[gems[start]] == 0: 개수가 0이 되면 gem_count에서 그 보석을 삭제
• start += 1: start 포인터를 오른쪽으로 이동

 

---

전체 코드

 

 

 

def solution(gems):
    total_gems = len(set(gems))  # 보석의 종류 수
    gem_count = {}  # 현재 구간의 보석 개수를 저장할 딕셔너리
    start, end = 0, 0
    result = [0, len(gems)]  # 최소 구간 초기값 = 전체 구간
    
    while end < len(gems):
        # end 포인터를 이동시키며 보석 추가
        if gems[end] in gem_count: 
            gem_count[gems[end]] += 1
        else:
            gem_count[gems[end]] = 1
        end += 1
        
        # 모든 종류의 보석을 포함하는 구간이 될 때까지 start 포인터 이동
        while len(gem_count) == total_gems:
            # 현재 구간이 더 짧은 경우 갱신
            if end - start - 1 < result[1] - result[0]:
                result = [start, end - 1]
            
            # start 포인터가 가리키는 보석을 빼고 한 칸 이동
            gem_count[gems[start]] -= 1
            if gem_count[gems[start]] == 0:
                del gem_count[gems[start]]  # 개수가 0이 되면 해당 보석 제거
            start += 1
    
    # 진열대 번호는 1번부터 시작하므로 결과에 +1
    return [result[0] + 1, result[1] + 1]

 

 

+) 코드 최적화

효율성이 너무 떨어지는 것 같아서 코드를 더 간결하게 하려고 해봤다.

 

여기서 key를 받는 구간을 더 간단하게 코드작성을 할 수 있다

if gems[end] in gem_count: 
            gem_count[gems[end]] += 1
        else:
            gem_count[gems[end]] = 1

 

gems_count[gems[end]] = gems_count.get(gems[end],0) + 1 # 키가 존재하면 get으로 키값 얻기

 

 

<동작 방식>

1. gems_count.get(gems[end], 0): 현재 보석이 gems_count에 이미 있다면 해당 보석의 개수를 가져옴. 없다면 기본값 0을 반환
2. gems_count[gems[end]] = ... + 1: 기존 개수에 1을 더해 업데이트

ex) gems = ["Ruby", "Emerald", "Ruby"]이고 gems_count = {}인 상태에서 end = 0이라면

gems_count[gems[0]] = gems_count.get(gems[0], 0) + 1

gems[0]은 "Ruby"이므로
gems_count.get("Ruby", 0) + 1 == 0 + 1 == 1
gems_count["Ruby"] = 1

확실히 조금 더 줄어들었음