[프로그래머스/Lv.3] - 보석 쇼핑

문제 링크

아이디어 및 풀이

문제의 조건에서 $1 \le len(gems) \le 100,000$ 이므로, $O(N^2)=100억$으로 불가능하다.

처음에 떠올린 알고리즘은 다음과 같다.

• DP: 일단 2차원 리스트로 선언한다하면 $O(N^2)$와 다를게 없기 때문에 제외했다.
• 이분탐색: 이분탐색은 전제조건이 리스트의 정렬이고 이 문제는 정렬을 수행하게되면 원하는 답을 구할 수 없기때문에 제외했다.

보석의 구간을 구하는 것이니 투 포인터를 이용하면 되겠다고 생각했다.

코드

실패 코드

# 1-index
from collections import defaultdict

def solution(gems):
    def check_gems():
        return all(list(gem_dict.values()))
    
    answer = []
    
    # 딕셔너리 = (종류 : 개수)
    gem_dict = defaultdict(int)
    for gem in gems:
        gem_dict[gem] += 1
    
    n = len(gems)
    l, r = 0, n - 1
    can_change_l, can_change_r = True, True # 증감이 가능한지
    
    while l < r:
        while r > l and can_change_r:
            gem_dict[gems[r]] -= 1
            if gem_dict[gems[r]] == 0:
                gem_dict[gems[r]] += 1
                can_change_r = False
            else:
                r -= 1
        answer.append([l + 1, r + 1])
        
        while l < r and can_change_l:
            gem_dict[gems[l]] -= 1
            if gem_dict[gems[l]] == 0:
                gem_dict[gems[l]] += 1
                can_change_l = False
            else:
                l += 1
        answer.append([l + 1, r + 1])
        
        break
    answer.sort(key=lambda x: ((x[1] - x[0]), x[0]))
    
    return answer[0]

위 코드의 알고리즘은 다음과 같다.

1. 먼저 gems에 속해있는 모든 보석의 종류와 개수를 딕셔너리에 저장한다.
2. l = 0, r = n - 1에서 시작해서 투 포인터를 진행한다.
3. r부터 크기를 1씩 줄여보면서, 만약 줄였을 때 모든 보석이 속해있지 않다면 r을 1 증가시키고 더 이상 r을 변경할 수 없다는 Flag인 can_change_r을 False로 바꾼다.
   • 그리고 answer에 현재 범위를 추가한다.([l + 1, r + 1])
4. l을 1씩 증가시키면서, 만약 증가시켰을 때 모든 보석이 속해있지 않다면 l을 1 감소시키고 더 이상 l을 변경할 수 없다는 Flag인 can_change_l을 False로 바꾼다.
   • 마찬가지로 answer에 현재 범위를 추가한다.([l + 1, r + 1])

어떤 오류가 존재할까?

위 코드는 r을 먼저 줄이고 l을 키우면서 범위를 확인한다.
이렇게 되면 초기 r일 때 범위를 확인할 수 없다.

예를 들어 [l + 3, r - 2]가 모든 보석을 포함하는 가장 짧은 구간이라고 하자.
r을 먼저 줄일 때 r - 4까지 줄일 수 있다고 하자.(즉, r - 5까지 줄이면 모든 보석을 포함하지 않는다.)

그 다음으로 l을 증가시키면, l의 크기가 어쨌든 r - 2까지의 범위는 구할 수 없다.
r이 이미 r - 4이기 때문이다.

✅ 투 포인터는 l과 r이 모두 0에서부터 시작한다.
내 코드는 r = n - 1에서 시작하므로, 투 포인터 알고리즘이라고 부를 수 없어보인다.

투 포인터 개념에 대해서 다시 한번 공부해야겠다.

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	실패 (0.03ms, 10.2MB)
테스트 3 〉	실패 (0.16ms, 10.1MB)
테스트 4 〉	통과 (0.20ms, 10.2MB)
테스트 5 〉	통과 (0.14ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	실패 (0.01ms, 10.2MB)
테스트 8 〉	실패 (0.27ms, 10.1MB)
테스트 9 〉	실패 (0.42ms, 10.4MB)
테스트 10 〉	통과 (0.35ms, 10.2MB)
테스트 11 〉	통과 (0.44ms, 10.3MB)
테스트 12 〉	실패 (0.69ms, 10.2MB)
테스트 13 〉	실패 (1.23ms, 10.3MB)
테스트 14 〉	통과 (0.80ms, 10.3MB)
테스트 15 〉	실패 (1.19ms, 10.4MB)
효율성  테스트
테스트 1 〉	실패 (5.79ms, 10.5MB)
테스트 2 〉	실패 (1.91ms, 10.5MB)
테스트 3 〉	실패 (4.93ms, 11MB)
테스트 4 〉	통과 (3.38ms, 11.7MB)
테스트 5 〉	실패 (7.25ms, 11.8MB)
테스트 6 〉	실패 (16.18ms, 12.2MB)
테스트 7 〉	실패 (10.26ms, 12.6MB)
테스트 8 〉	실패 (12.70ms, 13MB)
테스트 9 〉	실패 (15.75ms, 13.5MB)
테스트 10 〉	실패 (15.38ms, 13.9MB)
테스트 11 〉	실패 (19.43ms, 14.7MB)
테스트 12 〉	통과 (11.88ms, 15.5MB)
테스트 13 〉	실패 (16.72ms, 16.2MB)
테스트 14 〉	실패 (29.89ms, 17MB)
테스트 15 〉	통과 (32.08ms, 17.9MB)

정확성: 15.6
효율성: 13.3
합계: 28.9 / 100.0

성공 코드

# 1-index
from collections import defaultdict

def solution(gems):
    answer = []
    n = len(gems)
    set_size = len(set(gems))
    gem_dict = {gems[0]: 1}
    l, r = 0, 0
    can_change_l, can_change_r = True, True # 증감이 가능한지
    
    while l < n and r < n:
        # 모든 보석 종류가 범위 안에 존재한다면
        if len(gem_dict) == set_size:
            answer.append([l + 1, r + 1])
            gem_dict[gems[l]] -= 1
            
            if gem_dict[gems[l]] == 0:
                del gem_dict[gems[l]]
            
            l += 1
        else:
            r += 1
            if r == n:
                break
                
            gem_dict[gems[r]] = gem_dict.get(gems[r], 0) + 1
            
    answer.sort(key=lambda x: ((x[1] - x[0]), x[0]))
    
    return answer[0]

l, r을 모두 0부터 시작한다.

보석의 종류는 딕셔너리에 저장하고, 모든 보석을 포함할 때 까지 r 포인터를 증가시키고, 해당 위치의 보석을 딕셔너리에 추가 or 갱신한다.(단, 범위에 벗어나지 않도록)

모든 보석의 종류를 포함한다면, 구간을 저장하고 l을 증가시켜서 가장 짧은 구간을 찾는다.