[2020 카카오 인턴십] 보석 쇼핑

코딩테스트 연습 - 보석 쇼핑

 

풀이

 두개의 포인터를 이용하여 문제를 해결할 수 있다. 두 포인터를 left와 right라고 했을 때(left < right), 포인터를 이동시키는 과정은 다음을 따른다.

1. 두 포인터가 가르키고 있는 보석의 종류가 같을 경우
   -> left를 이동시켜서 구간의 길이를 감소시킨다. left가 가르키고 있는 보석은 right에 이미 있으므로 left에 있는 보석은 구간에서 제외해도 상관없다. 구간의 길이가 줄어들었으므로 기존의 가장 짧은 구간과 비교하여 더 짧은 구간으로 답을 갱신한다.
   
   
2. 두 포인터가 가르키고 있는 보석의 종류가 다를 경우
   1. right가 가르키고 있는 보석이 처음 등장한 보석일 경우 
      -> 새로운 종류의 보석을 포함한 구간으로 답을 갱신한 후 right를 이동시킨다.
       
   2. 현재 구간에서 left가 가르키고 있는 보석의 개수가 right가 가르키고 있는 보석의 개수보다 많을 경우
      -> left를 이동시켜 구간의 길이를 감소시킨다. left가 가르키고 있는 보석은 현재 구간 안에 2개 이상이므로 left에 있는 보석은 제외해도 상관없다. 구간의 길이가 줄어들었으므로 기존의 가장 짧은 구간과 비교하여 더 짧은 구간으로 답을 갱신한다.
      
      
   3. 현재 구간에서 right가 가르키고 있는 보석의 개수가 left가 가르키고 있는 보석의 개수보다 많거나 같을 경우 
      -> right를 이동시켜 구간의 길이를 늘린다. left에 있는 보석의 개수가 구간 내에 1개라면 left가 가르키고 있는 보석을 제거해서는 안된다. 따로 조건을 주어 이를 분리할 수 있지만 1과 2-2를 통해서 구간을 줄여나갈 수 있기 때문에 이 경우에는 right를 늘려 준다.

 

 위와 같은 규칙으로 포인터를 적절하게 이동시켜 구간의 길이를 구해줄 수 있다.

 

코드

def solution(gems):
    start, end = 0, 0 # 모든 종류의 보석을 담은 구간 중 가장 짧은 구간
    left, right = 0, 1 # 탐색에 사용될 포인터 

    gemDict = {gems[left]: 1} # 각 보석이 [left, right]에 몇 개인지를 체크하기 위한 딕셔너리
    change = right # left와 right중 이동한 포인터를 기록하기 위한 변수 

    while True:
        if right == len(gems): # right가 gems 배열을 벗어나면 while문 종료
            break

        if left == right: # left와 right가 같은 곳에 위치하면 right를 이동시킴
            right += 1
            change = right
            continue

        leftGem, rightGem = gems[left], gems[right] # 두 포인터가 가르키고 있는 구간 내에서 각 보석의 개수 

        # right가 가르키고 있는 보석이 새로운 종류일 경우 
        if rightGem not in gemDict: 
            gemDict[rightGem] = 1 # 딕셔너리에 보석 등록 
            start, end = left, right # 새로운 보석을 포함하고 있는 범위로 start와 end 업데이트 
            right += 1 # 그 후 right를 이동시킨다.
            change = right
            continue

        if change == right: # 이전에 이동시킨 포인터가 right일 경우 딕셔너리에 카운트
            gemDict[rightGem] += 1

        # 각 포인터가 가르키고 있는 보석의 개수 
        leftGemCount, rightGemCount = gemDict[leftGem], gemDict[rightGem]

        # 1-1. 두 포인터가 가르키고 있는 보석이 같은 보석이거나 
        # 1-2. 현재 구간에서 left가 가르키고 있는 보석의 개수가 right가 가르키고 있는 보석의 개수보다 많을 경우 
        if leftGem == rightGem or leftGemCount > rightGemCount:
            left += 1 # left를 한 칸 이동시킨다.
            change = left
            gemDict[leftGem] -= 1 # 기존의 left가 가르키고 있던 보석의 개수를 감소시킨다.

            # left가 이동했기 때문에 범위의 길이가 줄어들었으므로 길이를 비교하여 더 짧아졌을 경우 구간 정보를 갱신한다.
            if (right - left) < (end - start):
                start, end = left, right
        else: # 2. 두 포인터가 가르키고 있는 보석의 종류가 다르고 right가 가르키고 있는 보석의 개수가 left가 가르키고 있는 보석의 개수보다 많거나 같을 경우
            right += 1 # right를 한 칸 이동시킨다.
            change = right # 이 경우 구간의 길이가 늘어났으므로 구간 정보 갱신 여부를 체크할 필요가 없다.

    return [start + 1, end + 1]