[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/67258
📌문제 설명
개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.제한사항
- gems 배열의 크기는 1 이상 100,000 이하입니다.
- gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
- gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
- gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.
💡 문제 풀이
정확성과 효유성 모두 만족시켜야 정답이 처리되는 문제...!!!
(= 자료구조 이해에 대한 중요성)
gems 배열의 크기는 1 이상 100,000 이하이기 때문에, 이중 반복문은 효율성을 만족시키지 못할것이 뻔했다.
이중 반복문으로 보통 문제를 해결하지 못하면 '투 포인터'방법으로 문제를 해결한다고 한다.
따라서, 이 문제도 시작지점, 끝지점 두 개의 포인터를 설정하여 정답을 찾았다.
step 1)
변수 선언
- left : 시작지점(for 탐색)
- right : 끝지점(for 탐색)
- start : 가장 작은 구간의 시작지점
- length : 가장 작은 구간의 길이
step 2)
문제 해결을 위한 단계는 다음과 같다.
- left, right 값을 조절하여 슬라이싱 한다.(gems[left:right+1])
- 슬라이싱한 결과에 모든 종류가 담겨 있는지 확인한다.
- 만약, 모든 종류가 담겨 있다면 가장 작은 구간의 길이인지 비교하고 length, start 값을 최신화 한다. 이후 left값을 1 증가시킨다.
- 만약, 모든 종류가 담겨 있지 않다면 구간의 길이를 넓혀야 하므로 right값을 1 증가시킨다.
투 포인터는 gems 배열안의 특정 값을 가리키는 인덱스다.
따라서, 두 개의 값이 gems 범위 밖에 벗어나면 탐색을 마친다.
코드는 다음과 같다.
효율성 실패 - 시간초과
def solution(gems):
candidates = set(gems)
if len(candidates) == 1:
return [1, 1]
elif len(candidates) == len(gems):
return [1, len(gems)]
else:
left, right = 0, 0
start = int(1e9)
length = int(1e9)
while left < len(gems) - len(candidates) and right < len(gems):
if len(set(gems[left:right+1])) == len(candidates):
if right - left < length:
length, start = right - left, left
left += 1
else:
right += 1
return [start+1, start+length+1]정답을 제출했을 때 효율성 부분에서 시간초과가 발생했다.
아무래도 슬라이싱 작업이 시간복잡도를 증가시킨 것 같다.
※ 슬라이싱의 시간복잡도는 슬라이싱되는 요소들 수 만큼 비례한다.
ex) li[a:b] → O(b-a)
문제 해결을 위해서 딕셔너리 자료구조를 이용했다.
기존에는 원하는 구간을 슬라이싱하여 비교하였지만 딕셔너리를 이용하면 자료를 '종류'(key) - '개수'(value)형식으로 담아둘 수 있어서 단순히 개수만 파악하면 된다.
자료구조의 차이만 존재할 뿐 순서는 동일하다.
키(keys)의 길이(len)를 이용하여 모든 자료를 포함하는지 확인하고 그렇지 않을 경우 right+1해준다.
만약, 모든 자료를 포함하면 left+1 해주면서 가장 작은 구간의 길이를 구해주면 된다.
코드는 다음과 같다.
정답
def solution(gems):
kinds = len(set(gems))
gems_dict = {gems[0]:1}
answer = [0, len(gems) - 1]
left , right = 0, 0
while(left < len(gems) and right < len(gems)):
if len(gems_dict) == kinds:
if right - left < answer[1] - answer[0]:
answer = [left, right]
if gems_dict[gems[left]] == 1:
del gems_dict[gems[left]]
else:
gems_dict[gems[left]] -= 1
left += 1
else:
right += 1
if right == len(gems):
break
if gems[right] in gems_dict.keys():
gems_dict[gems[right]] += 1
else:
gems_dict[gems[right]] = 1
return [answer[0]+1, answer[1]+1]