[알고리즘_카카오 인턴] 보석 쇼핑 (파이썬)_투포인터

[알고리즘_카카오 인턴] 보석 쇼핑 (파이썬)_투포인터

 

무넺 자체가 정확성과 효율성 테스트이면 단순하게 안풀린다는 얘기...

gems 배열의 크기가 100,000 이하여야하기 때문에 꽤 빡센 조건이다.

 

연속된 구간에 대한 문제이므로 투포인터를 이용할 수 있는 문제.

 

투포인터를 이용한 첫 시도

 

def solution(gems):
    answer = []
    answer1 = []
    tmp = []
    n = len(gems)
    m = len(set(gems))
    end = 0 # index
    minv = 100000

    for start in range(len(gems)):
        while len(set(gems[start:end+1])) < m and end < n:
            end += 1
        
        if len(set(gems[start:end+1])) == m:
            answer.append([start+1,end+1])
        end = start +1
    
    for i in answer:
        if i[1]-i[0] < minv:
            minv = i[1]-i[0]
            answer1 = i
    
    return answer1

 

시간 초과.

gems의 배열 크기가 100000이하기 떄문에 시간 초과가 나왔다..

시간 복잡도를 O(n^2)에서 O(n)으로 줄여야한다.

 

두 번째 시도

 

def solution(gems):
    answer = []
    
    n = len(gems)
    m = len(set(gems))
    # index
    start = 0
    end = 0 
    # 현재 선택된 보석들
    curr = {gems[0]:1}
    
    while start < n or end < n:
        # 종류가 부족한 경우
        if len(curr) < m:
            end += 1
            if end == n:
                break
            # end를 curr에 추가
            # if curr[gems[end]] != 0: # 이건 안됨...
            if gems[end] in curr.keys():
                curr[gems[end]] += 1
            else:
                curr[gems[end]] = 1
        # 종류가 같은 경우
        else:
            answer.append(([start+1,end+1], end-start))
            curr[gems[start]] -= 1
            # curr value가 0이면 없애줘야 함. len(curr) 개수
            if curr[gems[start]] == 0:
                del curr[gems[start]]
            start += 1
    answer = sorted(answer, key=lambda x :(x[1], x[0]))    
    return answer[0][0]

 

key value가 익숙하지 않아서 나에겐 굉장히 어려운 문제였다.

if gems[end] in curr.keys(): # O
if curr[gems[end]] != 0 : # X

특히 위 박스에서 두번째 처럼 처음에 구현했는데, 틀린 게 이해가 되지 않았다.

dictionary에서 특정 key값이 없으면 그 값에 대응되는 value를 지정하거나 연산은 가능 (아래 박스)

하지만, 그 값 자체가 0인지 확인하는 것은 에러 !

if gems[end] in curr.keys():
	curr[gems[end]] += 1 # value 연산
else:
	curr[gems[end]] = 1 # value 지정

 

그리고 정렬문제 sorted(answer, key=lambda x: ~) 도 안보고 구현할만큼 익숙해질 필요가 있겠다.