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

Junyoung Park·2022년 2월 21일
0

코딩테스트

목록 보기
67/631
post-thumbnail

1. 문제 설명

보석 쇼핑

2. 문제 분석

정해진 목록 안에 모든 종류의 보석이 들어가야 한다. 이때 가장 짧은 목록을 구하자.

  1. 보석 종류를 카운트하면서 시작점과 끝점을 주어진 목록 상에서 이동해가며 확인하는 투 포인터 문제다.
  2. 끝점을 이동해가면서 모든 종류의 보석을 포함했는지 시작점을 이동해가며 최단 거리를 단축할 수는 없는지 확인한다.
  3. 끝점이 마지막 목록에 도달했을 때 가지고 있는 result가 곧 반환할 최단 거리의 인덱스 정보.
  • 끝점 end와 시작점 start를 언제 1씩 더해가면서 포인터를 이동할지가 헷갈렸다. 투 포인터 문제는 LV3을 풀기 위한 핵심적인 알고리즘이기 때문에 다른 유형에서도 잘 풀 수 있도록 연습하자.

  • start < end가 최단 거리 찾기, end < total_len이 투 포인터 조건으로 사용되니, 어떤 사항을 기준으로 포인터를 옮기는지 잘 파악하자.

3. 나의 풀이

def solution(gems):
    result = [1, len(gems) + 1]
    # [1번, 마지막 번호]: 탐색 이전 기본값
    start, end = 0, 0
    # 투 포인터로 start, end 지점 검색
    total_gems = len(set(gems))
    gem = {}
    # 범위 안에 들어 있는 보석 개수가 전체 보석 종류의 개수와 같은지 확인

    while end < len(gems):
        # 마지막 보석까지 end 포인터를 이동시키며 최단 거리를 확인하자.
        gem_name = gems[end]
        gem_cnt = gem.get(gem_name, 0)
        gem_cnt += 1
        gem[gem_name] = gem_cnt

        # 범위 내 보석 종류 개수에 end가 가리키는 보석을 추가한다.

        end += 1

        if len(gem) == total_gems:
            # 지금 모든 종류의 보석을 가지고 있다면
            while start < end:
                gem_name = gems[start]
                gem_cnt = gem.get(gem_name, 0)

                if gem_cnt > 1:
                    gem_cnt -= 1
                    gem[gem_name] = gem_cnt
                    start += 1
                    # 각 보석은 하나씩만 가져도 된다.
                else:
                    if end - start <= result[1] - result[0]:
                        result = [start + 1, end]
                        break
                        # 보석 종류를 포함한 최단 거리를 갱신한다.
                        # start에 1을 더해 zero base 인덱스를 수정한다.
                        # end는 앞에서 (최단 거리가 있든 없든) +1 해주었기 때문에 이 시점에서 자동으로 처리된다.
                    else:
                        break
    return result
profile
JUST DO IT

0개의 댓글