[프로그래머스] 67258. 보석 쇼핑

2020 카카오 인턴십 - 67258. 보석 쇼핑

Python 풀이

 

풀이 1

Two Pointer(투 포인터) 알고리즘을 이용해 풀이.

외국에선.. Two Pointer Technique(투 포인터 테크닉) 이라고 부르는 듯.

 

start, end Pointer를 정하고,

처음엔 조건을 만족할 때까지 end += 1

그 이후, 조건을 만족하는 한 start += 1

그렇게 조건을 만족하는 [start, end]를 구함.

 

그 이후, 뒤쪽에 더 짧은 답이 존재할 수 있으니

end에 +1을 해주며, end < len(gems) 이하에서 반복.

 

그렇게 Two Pointer를 이용해 풀이하였으나,

시간 초과.

 

Code

def solution(gems):
    gemList = len(set(gems))
    start = 0
    end = 0
    answer = [0, len(gems)]
 
 
    def A():
        a = len(set(gems[start:end+1]))
        if a == gemList:
            return True
        else:
            return False
 
 
    while True:
        while True:
            if A():
                break
            end += 1
 
        while True:
            start += 1
            if A() == False:
                start -= 1
                break
 
        if (answer[1]-answer[0]) > (end - start):
            answer = [start, end]
 
        if end == len(gems)-1:
            break
        else:
            end += 1
            
    return [answer[0]+1, answer[1]+1]

 

 

풀이 2

위의 방법은,

def A():
    a = len(set(gems[start:end+1]))
    if a == gemList:
        return True
    else:
        return False

를 각 순회마다 실행하는 데다, 위 함수 자체가 리스트를 슬라이싱 후 하나하나 set으로 변경하기에 시간이 오래 걸린다.

 

따라서, 구간이 모든 보석을 하나 이상 포함하는 지 검사할 때, 그 때마다 리스트를 슬라이싱해 검사하지 말고,

dictionary를 이용하면 key값의 개수만 세고도 검사할 수 있다.

진열대 번호	1	2	3	4	5	6	7	8
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERALD	SAPPHIRE	DIA

에서 [3, 7]의 구간을 dictionary로 표현한다면, DIA가 2개, RUBY 1개, EMERALD 1개, SAPPHIRE 1개이므로

{DIA: 2, RUBY: 1, EMERALD: 1, SAPPHIRE: 1} 과 같이 만들 수 있다.

이렇게 되면, dictionary의 key 개수만 비교한다면 구간이 모든 보석을 하나 이상 포함하는 지 검사할 수 있기에, 시간이 단축된다.

 

Two Pointer를 이용해 구간을 탐색하면서, end += 1을 할 때는 key값이 존재한다면 value를 +1, key값이 없다면 key값을 추가하고,

start += 1을 하여 구간의 길이가 줄어들었을 때는, value == 0 이 된 key값이 있다면 그 key값을 삭제해 주며 반복한다.

 

위와 같은 예시에서는, [3, 7]의 구간에서 start += 1을 하여 [4, 7]의 구간으로 변경한다면,

{DIA: 2, RUBY: 0, EMERALD: 1, SAPPHIRE: 1} 이 되는데, RUBY는 0개(구간에 포함되지 않음) 이므로,

{DIA: 2, EMERALD: 1, SAPPHIRE: 1} 와 같이 수정해주는 식으로 진행하면 된다.

 

Code

def solution(gems):
    gemList = {gems[0]: 1}
    start = 0
    end = 0
    answer = [0, len(gems)]
 
    kindOfGem = len(set(gems))
 
 
    def add(gem):
        if gem in gemList:
            gemList[gem] += 1
        else:
            gemList[gem] = 1
 
 
    def remove(gem):
        if gemList[gem] == 1:
            del gemList[gem]
        else:
            gemList[gem] -= 1
 
 
    while start <= end and end < len(gems):
        if kindOfGem == len(gemList):
            if answer[1]-answer[0] > end-start:
                answer = [start, end]
            remove(gems[start])
            start += 1
 
        elif kindOfGem != len(gemList):
            end += 1
            if end == len(gems):
                break
            add(gems[end])
            
    return [answer[0]+1, answer[1]+1]

 

이 부분에서 조건을 달아 break하는 방식과, 다른 loop 방식으로 풀이하려 해서 어려움을 겪었는데,

아래 블로그의 코드를 참고하여 해결하였다.

>> Reference <<

	while start <= end and end < len(gems):
        if kindOfGem == len(gemList):
            if answer[1]-answer[0] > end-start:
                answer = [start, end]
            remove(gems[start])
            start += 1
 
        elif kindOfGem != len(gemList):
            end += 1
            if end == len(gems):
                break
            add(gems[end])