[Programmers] - 보석 찾기 (2020 카카오 인턴십) with Python

📎 간략한 문제 정리

• 전체 배열의 모든 요소를 가진 set이 있을 때, 이 set의 모든 요소를 가진 배열의 부분 배열 중 최소의 길이를 가진 구간을 찾는 문제입니다.

📈 문제 분석

• 단순히 전체 순회를 하면 속도 이슈가 발생할 수 밖에 없습니다. 범위가 100,000 이므로 O(N^2)이면 바로 속도 이슈가 발생합니다(100번 연산). 아주 단순한 생각으로는 for문을 2차원으로 돌려 i와 j를 정하고, [i:j] 구간에서 모든 요소를 갖는지 검색해보면 되겠지만 이 검색 역시도 cost가 발생하는데다가 검색 자체에서 이미 속도를 넘어서므로 더 효율적인 방법이 필요합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 저는 슬라이딩 윈도우를 생각했고, 이 슬라이딩 윈도우의 크기를 이분탐색을 통해 찾는 방식을 생각했습니다. 예시는 모두 통과하고 문제 풀이 결과도 일부 통과하지만 틀린 문제도 있었습니다. 이유를 더 생각해볼 필요가 있습니다. 그래서 저는 투포인터의 조건을 주어 문제를 해결했습니다.

💻 풀이한 코드

def solution(gems):
    from collections import defaultdict
    target = len(set(gems))
    left, right = 0, 0
    check_dict = defaultdict(int)
    check_dict[gems[left]] = 1
    cache = [0, len(gems) - 1]
    while left < len(gems) and right < len(gems):
        if len(check_dict) == target:
            if right - left < cache[1] - cache[0]:
                cache = [min(left, right), max(left, right)]
            check_dict[gems[left]] -= 1
            if check_dict[gems[left]] <= 0:
                del check_dict[gems[left]]
            left += 1
        else:
            right += 1
            if right < len(gems):
                check_dict[gems[right]] += 1
    return [cache[0] + 1, cache[1] + 1]

📝 해결 과정에서 만난 문제, 고민들

• 투포인터:
  투포인터에서 가장 중요한 점은 관찰 왼쪽과 오른쪽의 시작 지점이 같다는 점, 그리고 왼쪽을 올리거나 오른쪽을 올릴 때의 조건을 엄밀하게 정의하는 것이었습니다. 이 문제처럼 전체 구간에서 일부 구간을 검색해야할 때, 특정 조건이 만족하는지 확인해야한다면 효율적인 방식일 수 있습니다.

• 슬라이딩 윈도우 + 이분탐색:

  def solution2(gems):
      left, right = 0, len(gems) - 1
      target = len(set(gems))
      cache = [left+1, right+1]
      while left <= right:
          is_check = False
          mid = (left + right) // 2
          for i in range(len(gems)-mid+1):
              if len(set(gems[i:i+mid])) == target:
                  if cache[1]-cache[0] > mid or (cache[1]-cache[0] == mid and cache[0] > i+1):
                      cache = [i+1, i+mid]
                  is_check = True
                  break
          if is_check:
              right = mid - 1
          else:
              left = mid + 1
      return cache

  기본적으로 슬라이딩 윈도우는 크기가 정해진 만큼씩만 이동하며 구간을 살피는 것이기 때문에 O(N)으로 가능합니다. 중요한 것은 이 윈도우의 크기인데 이분탐색을 통해 O(logN)으로 계산하면 속도 이슈가 발생하지 않을 수 있다고 생각했습니다. 주어진 조건에서 O(NlogN)은 통과 가능한 수치이기 때문입니다. 해당 길이로 모든 요소를 포함하는 부분 배열이 있을 경우 더 작은 크기를 탐색하는 과정을 반복하는 방식인데 왜 안되는지 더 생각해볼 필요가 있습니다. 고민되는 코드는 아래와 같습니다.

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