[프로그래머스] 보석 쇼핑 (2020 KAKAO INTERNSHIP) / python

1. 문제 설명

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

어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

보석 이름

DIA

RUBY

RUBY

DIA

DIA

EMERALD

SAPPHIRE

DIA

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.
진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이
때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며,
만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한사항

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

입출력 예

gems result

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
["AA", "AB", "AC", "AA", "AC"]	[1, 3]
["XYZ", "XYZ", "XYZ"]	[1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"]	[1, 5]

 

2. 풀이 전 계획과 생각

구하고자 하는 바

→ 가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return

gems의 배열의 길이는 10^5이다.

 

보석의 개수를 실시간으로 확인하기 위해 HashMap을 사용하여, count를 저장해둔다.
완전탐색을 사용하여 모든 구간을 확인하려면 O(N^2)이 된다. → 시간 초과

구간에 대한 탐색의 범위를 줄이기 위해, 투포인터를 사용해주자. O(N)

 

3. 풀이하면서 막혔던 점

투포인터를 사용하려고 했는데,

• → →로 접근할 경우
  L과 R를 증가시켜줘야 하는 point를 찾아주지 못했다.
• → ←로 접근할 경우
  
  • dict 배열이 다 1개 이상씩 존재한다면, 이동한다.
    두개다 각각 이동하되, 이동하면서 dict 배열의 연산을 수행한다.
  • 만약에 dict 배열이 다 1개이상 존재 하지 않는다면 이동하지 않는다.
  • 다 탐색해주면 최악의 경우 O((N+1)*N/2) ⇒ O(N^2)이 나온다.
    (비효율적이다. 해시테이블이 다 1개 이상 존재해야하는지 체크해줘야 한다.)

 

🤔 → →로 접근할 경우 L과 R을 증가시켜줘야 하는 point는 언제일까?

• 보석이 충분하지 않으면, R 이동
• 보석이 충분하면, L 이동
• dict는 이동할 때마다 갱신한다.

 

🤔 해시테이블을 일일히 체크해주지 않으려면?

해시테이블을 { 각 원소 : 0 }로 초기화해주지 말자.

그리고 해시테이블의 길이를 연산하는 함수를 사용하면 된다.

 

4. 풀이 전 계획과 생각

• L과 R을 0으로 둔다.
• L과 R에 따른 해시테이블을 계산한다.

 

• 보석이 충분하지 않으면 R을 이동한다. 해시테이블 갱신한다.
• 보석이 충분하면 L 이동한다. 해시테이블 갱신한다.
• (map의 길이가 set(gems)이면 len -= 1을 하고 종료한다.)
• L로 이동할 때, 해시테이블의 값이 0이면 해당 key를 삭제한다.

 

5. 풀이

def solution(gems):
    dict = {}
    left, right = 0, 0
    gems_kind = len(set(gems))
    gems_length = len(gems)
    
    # 보석이 충분하지 않으면 R을 이동
    while True:    
        if dict.get(gems[right], False):
            dict[gems[right]] += 1
        else:
            dict[gems[right]] = 1
        
        if len(dict) == gems_kind:
            break
        
        right += 1
    
    # 보석이 충분하면 L 이동
    while True:
        dict[gems[left]] -= 1
        
        if dict[gems[left]] == 0:
            del dict[gems[left]]
            break
        
        left += 1
            
    answer = [left + 1, right + 1]
    return answer

 

문제점

• 반례가 있다. ["A","B","B","B","B","B","B","C","B","A"]
• L과 R을 동시에 움직여야 한다. 왜냐하면, 뒤에 보석이 충분하고, 적은 범위가 있을 수 있기 때문이다.

 

6. 2차 풀이

• Left 이동하는 기준
  • 범위 안에 보석 종류가 찼다면, 구간의 길이를 체크해주어 답을 갱신하고, 더 짧은 구간이 있는지 확인하기 위해 Left가 이동한다.
• Right 이동하는 기준
  • 아직 범위 안에 보석 종류가 전체 보석 종류보다 작다면, Right가 이동한다.

def solution(gems):
    gem2cnt = {gems[0] : 1}
    gem_total_cnt = len(set(gems))
    l_idx, r_idx = 0, 0
    answer = [1, len(gems)]
    
    while l_idx <= r_idx < len(gems):
        # Left 이동하는 기준 : 범위 안에 보석 종류가 찼다면, 
        if len(gem2cnt) == gem_total_cnt:
            # 구간의 길이를 체크해주어 답을 갱신
            if r_idx - l_idx < answer[1] - answer[0]:
                answer = [l_idx + 1, r_idx + 1]
            # 더 짧은 구간이 있는지 확인하기 위해 Left가 이동
            gem2cnt[gems[l_idx]] -= 1
            if gem2cnt[gems[l_idx]] == 0:
                del gem2cnt[gems[l_idx]]
            l_idx += 1
        # Right 이동하는 기준 : 아직 범위 안에 보석 종류가 전체 보석 종류보다 작다면,
        else:
            # Right가 이동
            r_idx += 1
            if r_idx >= len(gems):
                break
            if gems[r_idx] in gem2cnt:
                gem2cnt[gems[r_idx]] += 1
            else:
                gem2cnt[gems[r_idx]] = 1
            
    
    return answer

 

7. 풀이 후 알게된 개념과 소감

• 투포인터를 통해 탐색의 시간을 줄일 수 있다. 동시에 L, R을 이동해야 모든 경우를 탐색한다.
• 구간에 대한 탐색의 시간을 줄이기 위해 투포인터를 사용해주었는데,
  count를 저장하는 자료구조를 사용해줌으로써 바로 보석의 개수를 실시간으로 확인해줄 수 있었다.