보석 쇼핑

문제

모든 유니크한 원소들로 구성된 서브 배열의 길이가 최소값일때 위치를 구하는 문제이다.

중복되는 길이의 경우 더 앞의 배열이 우선된다.

 

풀이방법

투포인터로 푼다.

포인터 안에 들어갈 경우 카운트하고, 밖으로 나갈경우 카운트에서 제외한다.

모든 원소들이 있는 경우 left를 +1하고,

모든 원소가 있는게 아니라면 right를 +1한다.

다만, 한번 배열을 찾았다면 더 긴 배열은 필요없으므로, 그때부터는 right가 이동할때 left도 함께 이동한다.(슬라이딩 윈도우)

 

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

def solution(gems):
    gems_count = {k: 0 for k in (set(gems))}
    pos1, pos2 = 0, 0
    gems_count[gems[pos1]] += 1
    min_length = len(gems) + 1
    answer = []
    while True:
        if 0 in gems_count.values():
            if pos2+1 == len(gems): # 포인터가 범위를 벗어난 경우
                break
            elif pos2 - pos1 == min_length: # 이미 더 적은 길이가 있어서 궂이 더 긴 길이가 확인이 필요없는 경우
                gems_count[gems[pos1]] -= 1
                pos1 += 1
                pos2 += 1
                gems_count[gems[pos2]] += 1
            else:
                pos2 += 1
                gems_count[gems[pos2]] += 1
        else:
            if pos2-pos1 < min_length:
                answer = [pos1+1, pos2+1]
                min_length = pos2-pos1
            gems_count[gems[pos1]] -= 1
            pos1 += 1
    return answer


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