2021 KAKAO 채용연계형 인턴쉽 보석 쇼핑

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

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

 

처음에는 naive한 방식을 생각하다가, 특정 영역 [a,b] 영역을 확인한 결과를 사용할 수 없을까라는 생각을 했다.
그래서 떠올린 방법이 2-pointer이다.

end가 증가하면서 확인하는 것은, 보석 종류를 확인하고, 해당 보석 개수를 기록하는 것이다. 해당 보석 종류가 처음 등장하면 이를 기록한다. 처음 등장하지 않더라도 일단 해당 종류의 보석 개수를 기록한다.

start가 2개이상 가지고 있는 보석을 가리키고 있다면  start를 증가시키면서 중복 보석들을 지운다. 이과정을 끝까지 반복하면서 최소 구간을 구하면 된다.

내 코드는 다음과 같다.

def solution(gems):
    answer = [0,len(gems)]
    
    info = dict()
    for gem in gems:
        if gem not in info:
            info[gem] = 0
    cnt = len(info)
    t = s = 0
    for e in range(len(gems)):
        info[gems[e]] += 1
        if(info[gems[e]] >= 2):
            while s < e:
                if info[gems[s]] >= 2:
                    info[gems[s]] -= 1
                    s += 1
                else:
                    break
        else:
            t += 1
        if t == cnt and answer[1] - answer[0] > e - s:
            answer = [s+1, e+1]
        
    return answer