[프로그래머스] 보석 쇼핑 (Python 파이썬)

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

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

문제 설명

위 링크에 나온 설명처럼, 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제입니다.

---

풀이 과정

이 문제는 투 포인터 유형의 문제입니다.

변수로 주어진 보석들의 목록인 gems에는 보석들이 중복되어 포함되어 있습니다.

그래서 보석의 종류만을 구하기 위해 set을 이용해 setlen에 보석의 종류를 넣어줬습니다.

 

start와 end를 처음지점으로 놓고, 최초의 길이는 처음부터 끝까지로 지정합니다.

end를 하나씩 늘려가며 범위를 넓혀갈건데

현재 지정한 범위에 모든 종류의 보석이 들어오게 되면

범위를 더 좁힐 수 있는지를 확인해야 합니다.

 

저 같은 경우는, 처음에 풀 때 마지막 부분의 elif부분을 구현하지 않아서 통과하지 못했습니다.

그래서 ["a", "b", "c", "b", "c", "d", "f", "d", "b", "e", "g", "e", "a"] 이런 케이스를 만들었더니

[5, 13] 이라는 더 짧은 구간이 있음에도 불구하고[1, 11]로 값을 반환한 것을 확인했습니다.

 

그 이유는, 뒤에 "e"와 "a"가 더 등장함에도 불구하고,

모든 종류의 보석이 구간안에 들어오면 앞의 start를 막았기 때문이었습니다.

 

이 부분을 꼭 고려하여 작성하시면 될 것 같습니다!

def solution(gems):
    answer = []
    setlen = len(set(gems)) # 보석의 종류수
    gemdict = {} # 보석 종류별로 개수를 셀 딕셔너리

    start = 0 # 투 포인터의 시작점
    end = 0 # 끝점
    sect = len(gems)+1

    while end < len(gems): # 끝점이 범위안에 있을 때만 검사

        if gems[end] not in gemdict: # 새로 발견한 보석
            gemdict[gems[end]] = 1
        else: # 기존에 존재하는 보석
            gemdict[gems[end]] += 1

        end += 1 #보석을 새로 추가했으니 end칸 한 칸 뒤로

        if len(gemdict) == setlen: # 범위안에 모든 보석이 존재할 때
            while start < end:
                if gemdict[gems[start]] > 1:  # 하나 이상 존재하면 뒤에도 더 존재한다는 뜻이므로
                    gemdict[gems[start]] -= 1  # 하나를 제거해주고
                    start += 1  # start칸을 뒤로 한칸 이동
                elif end-start < sect: # 지정한 구간보다 현재 구간이 짧으면
                    sect = end-start # 지정한 구간 바꿔주기
                    answer = [start+1, end]
                    break
                else:
                    break

    return answer

print(solution(["XYZ", "XYZ", "XYZ"]))

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !