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

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

 

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

• 제한사항

  • 어피치는 우선 일렬로 보석들을 한줄에 싹 쓸어담아 구매한다.
    • 배열의 구간을 띄워서 사지 않는다!
  • solution의 매개변수인 gems(보석 진열 배열)의 크기가 100,000 까지이다.
    • 100,000의 크기를 하나씩 일렬로 검사하는 것은 O(n * n)이므로 시간 초과가 발생할 것이다.

• 풀이전략

  • 먼저, 보석의 종류를 파악하기
    • set(gems)를 활용해 보석의 종류 수를 파악하기
    • 만약 종류가 1가지일 경우는 [1, 1] / 종류의 수와 배열의 크기가 같다면 [1, len(gems)]를 바로 리턴쳐주자.
  • dict 선언하기
    • { "보석" : 해당 보석의 갯수 } 의 형태
  • start, end 포인트를 지정하자.
    • start, end = 0, 0
    • start = 0인 이유?
      • 가장 짧은 구간이 여러개라면, 시작 진열대 번호가 가장 작은 구간을 return하기 때문!
  • 위의 선언한 변수들을 활용하여 dict의 크기 == len(set(gems))을 만족할 때 까지 end를 +1 해주기
    • end >= len(gems) 시 break
      • 이 때, 선언하는 위치가 중요하다. 코드를 보고난 다음에 설명하겠다.
  • len(dict) == len(set(gems))을 만족할 경우
    • 우선 기본으로 answer = [1, len(gems)]로 초기화 작업을 했다.
    • answer[1] - answer[0] + 1 = 갖고 있는 보석 수
    • end - start = while문을 돌면서 len(dict) == len(set(gems)) 조건을 만족했을 때, bucket에 담긴 보석의 갯수 (end -1 번째 인덱스 까지 보석을 갖고 있다.)
    • 이 둘중에서 answer[1] - answer[0] + 1이 클 경우에는 answer를 교체해준다.
    • 이 때 end는 다음 보석을 가질 수 있는 index를 가리키고 start는 보석의 첫번째를 가리킨다. 인덱스 그대로가 아닌 1~len(gems) 까지의 범위이므로 start + 1을 하여 answer 배열에 담아주자.

def solution(gems):
    # 보석 종류 파악하기
    kinds = set(gems)

    # 종류가 gems의 크기와 같거나 종류가 한 가지인 경우
    answer = [1, len(gems)]
    if len(kinds) == len(gems):
        return answer
    if len(kinds) == 1:
        return [1, 1]

    # 보석을 담을 dict
    bucket = dict()

    # while문을 사용하기 위해 start, end 지정
    start, end = 0, 0
    while True:
        if len(bucket) == len(kinds):
            if answer[1] - answer[0] + 1 > end - start:
                answer = [start + 1, end]

            if bucket[gems[start]] == 1:
                del bucket[gems[start]]
            else:
                bucket[gems[start]] -= 1
            start += 1
        else:
            # end의 인덱스를 앞에서 점검하자.
            if end >= len(gems):
                break
            if gems[end] not in bucket.keys():
                bucket[gems[end]] = 1
            else:
                bucket[gems[end]] += 1
            end += 1
            # 뭔 차이인가!
            # if end >= len(gems):
            #     break

    return answer

주석 처리한 if절의 의미

우선 if절을 주석한 부분에 위치시키면 end += 1을 연산하고 나서 담은 보석의 크기와 종류가 같을 수 있다. 나는 처음에 주석처리한 곳에 if절을 넣어 6, 7번 테스트케이스를 통과하지 못하였다.

if end >= len(gems)를 앞에서 처리하여 end가 가리키는 부분이 gems의 인덱스를 넘어서더라도 꼭 담은 보석의 크기와 종류가 같은지 체크할 수 있도록 수정했다.