[파이썬] 2020 카카오 인턴십 - 보석 쇼핑

문제

 

문제 바로가기: [프로그래머스]  2020 카카오 인턴십 - 보석 쇼핑

---

풀이

#처음에 풀 지 못해서 카카오 해설을 참고하였다

#투 포인터, 딕셔너리 활용

 

1. 범위의 시작을 나타내는 왼쪽 인덱스 포인터, 범위의 끝을 나타내는 오른쪽 인덱스 포인터를 사용했습니다

   - 두개의 포인터 모두 인덱스 0에서 시작합니다

2. 반복문을 통해 왼쪽 인덱스 고정, 오른쪽 인덱스는 하나씩 나아갑니다

   - 왼쪽 인덱스 또는 오른쪽 인덱스가 길이를 넘어가면 모든 것을 종료합니다

3. 오른쪽 인덱스의 해당하는 값들을 딕셔너리에 { 'RUBY': 빈도수 } 형태로 넣어 줍니다

  - 이미 딕셔너리에 있는 값이라면 빈도수 + 1을 해주고, 딕셔너리에 없었다면 값: 1 을 정의해줍니다

 

4. 위의 과정 중 오른쪽 인덱스가 하나씩 나아갈 때마다 딕셔너리에 넣어주는 값들의 종류의 갯수를 세어줍니다

  - 딕셔너리에 있는 값의 종류와 처음에 주어진 gems의 모든 종류의 갯수가 같다면 아래의 과정들을 따릅니다.

5. 현재 왼쪽 인덱스와 오른쪽 인덱스의 범위의 최소값 비교를 통해 answer에 해당 인덱스를 저장합니다

6. 왼쪽 포인터의 인덱스를 +1 해주고, 딕셔너리에서 해당 왼쪽 포인터의 인덱스에 해당하는 값을 삭제해줍니다

  - 딕셔너리에 {해당 값: 1번} 이였다면, 아에 삭제해줍니다

  - 딕셔너리에 {해당 값: 2번 이상} 이였다면, 빈도수 -1을 해줍니다

7. 다시 1번으로 돌아가 반복합니다

---

코드

def solution(gems):
    dictionary = {
        gems[0]: 1     #처음 값은 넣어줘야 함
    }
    
    left_index = 0
    right_index = 0
    
    ans_left_index = -987654321
    ans_right_index = 987654321
    
    kind_gems_len = len(list(set(gems)))
    gems_len = len(gems)
    
    while True:
        if left_index == gems_len or right_index == gems_len:
            break
            
            
        if len(dictionary) < kind_gems_len:
            right_index += 1
            if right_index == gems_len:
                break
            
            if gems[right_index] in dictionary:
                dictionary[gems[right_index]] += 1
            else:
                dictionary[gems[right_index]] = 1
        
        
        elif len(dictionary) == kind_gems_len:
            if (right_index - left_index)  <  (ans_right_index - ans_left_index):
                ans_left_index = left_index
                ans_right_index = right_index
        
            
            if dictionary[gems[left_index]] == 1:
                del dictionary[gems[left_index]]    #딕셔너리 삭제
            else:
                dictionary[gems[left_index]] -= 1
            
            left_index += 1
            
                
    return [ans_left_index+1,ans_right_index+1]

---

결과