🧐 문제 설명
😍 나의 풀이
이 문제는 투 포인터를 이용해서 효율성을 줄이는 문제인데, 투 포인터 문제를 앞서 접해 보았지만 이 문제에서 활용해야겠다고 전혀 생각지 못했다.
그래서 결국 카카오에서 제공한 문제 해설을 보고 코드를 짰다😖
카카오 문제 해설은 다음과 같다.
- 맵 자료구조에서, ‘map[보석 이름] = 빈도수’로 정의를 합니다.
- 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킵니다.
- 양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료합니다.
- 양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 봅니다.(map의 사이즈를 체크합니다)
5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l를 증가시킵니다. 그리고 2로 갑니다.
5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r를 증가시킵니다. 그리고 3으로 갑니다.
파이썬에서 map 자료 구조는 Dictionary를 사용하면 된다.
Left, Right 투 포인터를 생성한다.
🔎 Left : 딕셔너리에 보석 종류가 모두 있다면, 최소 크기를 확인 위해
1씩 우측으로 이동하며 확인(보석 빼는 용도)
🔎 Right : 딕셔너리에 보석 종류가 모두 없다면, 보석 추가를 위해
1씩 우측으로 이동하며 딕셔너리에 추가(보석 더하는 용도)
처음 투 포인터가 가리키는 시작 위치는 1번 진열대로 한다.
딕셔너리에 초기 값으로 1번 진열대의 보석을 Key 값으로 넣어주고 count 1한다. 딕셔너리에 보석의 종류가 모두 채워지지 않았으므로 Right를 1씩 우측으로 이동한다.
보석의 종류가 모두 채워질 때까지 Right를 증가 시키면서 딕셔너리의 Key와 Value(여기서는 빈도수 count)를 갱신하면서 Right가 6번 진열대에 오면 이제 최소 크기인지를 확인해야한다.
이제 Left를 우측으로 1씩 증가시키면서 이전 크기보다 최소 크기이면 answer의 인덱스를 갱신한다. 위 예시 같은 경우는 1~6번까지 'AAABBC' 보다 3~6번인 'ABBC'가 더 크기가 작으므로 이를 현재까지의 answer로 갱신하면 된다.
💡 이 때, 주의할 점은 여기서 멈추면 안되고 아직 체크해보지 않은 뒤쪽에서
최소 크기를 만족하는 인덱스 순서가 나올 수 있으니 left, right 포인터가
인덱스 범위를 벗어날 때까지 위 과정을 반복 진행해야한다.
이제 위와 같이, Left 포인터는 4번 위치, Right는 6번 위치에 있다. 딕셔너리에 A가 count가 0이 되어서 Key를 del 하였기 때문에 딕셔너리에는 보석의 종류가 모두 있지 않고 따라서 Right를 우측으로 1씩 증가시키면서 다시 확인한다.
다시 보석의 종류가 딕셔너리에 모두 Key로 생성되는 시점은 Right 포인터가 9번 위치에 있을 때이다. 4~9번 'BBCCBA'는 앞서 구했던 최소 크기인 answer 3~6번 'ABBC'보다 크므로 최소 크기로 선택하지 않고, Left를 1씩 우측으로 이동하면서 최소 크기를 다시 확인한다.
다음과 같이 Left가 이동하여 7번 위치에 있을 때 7~9번 'CBA'는 이전에 answer보다 최소 크기 이므로 answer를 이 값으로 최신화 한다.
Left, Right 투 포인터가 주어진 인덱스를 벗어나면 모두 탐색한 것으로 보고 현재까지 가장 최소 크기인 answer를 출력한다.
def solution(gems):
answer = [0, len(gems)]
size = len(set(gems)) # 보석 종류 갯수
left, right = 0, 0 # left는 보석 빼 줄 포인터, right는 보석 더해 줄 포인터
gem_dict = {gems[0] : 1}
while left < len(gems) and right < len(gems): # 투 포인터가 범위를 벗어나면 무한루프 종료
# 딕셔너리에 보석 종류가 다 들어오는 경우
if len(gem_dict) == size:
if right - left < answer[1] - answer[0]: # 최소 크기 확인
answer = [left, right]
else:
gem_dict[gems[left]] -= 1
if gem_dict[gems[left]] == 0:
del gem_dict[gems[left]] # count가 0이 되면 key가 없어야하므로 반드시 del
left += 1
else:
right += 1
if right == len(gems):
break
if gems[right] in gem_dict: # 딕셔너리 key에 있으면 count
gem_dict[gems[right]] += 1
else: # 없으면 추가
gem_dict[gems[right]] = 1
return [answer[0]+1, answer[1]+1] # 시작 인덱스가 1번 진열대 부터 라서 1 증가👏 다른 사람의 풀이
다른 사람의 풀이에서 한 가지 배울 점이 있었다.
나는 모든 보석이 딕셔너리에 key로 존재하지 않는 경우 right를 +1 하고 gems[right] 값이
- 딕셔너리에 key로 있으면 key에 해당하는 value(count)를 +1
- 딕셔너리에 key로 없으면 key를 추가하고 count를 1 할당
if gems[right] in gem_dict: # 딕셔너리 key에 있으면 count
gem_dict[gems[right]] += 1
else: # 없으면 추가
gem_dict[gems[right]] = 1하는 방식으로 코드를 짰다.
그런데 이 부분은 딕셔너리의 get 메소드를 이용하면 훨씬 간단하게 바꿀 수 있었다.
딕셔너리.get(key, default)딕셔너리에 key가 있으면 해당 key에 대한 값을 반환
딕셔너리에 key가 없으면 default에 지정한 값을 반환
이를 이용해서 다음과 같이 바꾸어서 조건문을 없애고 코드의 가독성을 살릴 수 있었다. 꽤 자주 보이는데 숙달이 아직 안된 것 같다😂
gem_dict[gems[right]] = gem_dict.get(gems[right], 0) + 1