서론
프로그래머스 - 2020 카카오 인턴십 보석쇼핑
https://school.programmers.co.kr/learn/courses/30/lessons/67258
해당 문제를 풀었을 때, set를 사용하여 시간을 단축시키려 했으나 효율성 테스트에서 실패했다.
많은 글들을 찾아봤으나 '해당 문제는 배열의 길이가 최대 100,000이므로 탐색 횟수를 줄여야 한다, 그러므로 투포인터를 사용해야 한다'는 설명만 있고, 어떤 방식을 사용해야 탐색 횟수를 가장 많이 줄일 수 있는지에 대한 설명은 없었다.
본 글쓴이는 탐색 시간을 줄이기 위해 투포인터와 set()를 사용했고, 이를 통해 탐색 시간을 어느정도 줄일 수 있었지만, 그것이 Best solution은 아니었던 것 같다.
set를 사용해서도 시간을 줄일 수 있지만, 딕셔너리라는 더 나은 솔루션이 존재했다. 왜 이 문제에선 딕셔너리가 set보다 더 나은 솔루션일까?
비슷한 경험을 하실 분들을 위해 해당 정보를 공유하고자 한다.
문제 풀이
1차 시도 - 완전 탐색, set 활용
결과: 시간 초과
def solution(gems):
answer = []
ngems = [0] + gems
kinds = set(gems)
need_count = len(kinds)
min_length = 100000
left = 1
right = 1
for right in range(1, len(ngems)):
for left in range(1, right + 1):
select = ngems[left:right + 1]
if len(set(select)) == need_count:
length = right - left + 1
if length < min_length:
min_length = length
answer = [left, right]
return answer
주어진 gems에 가장 앞 부분에 0을 붙여서 인덱싱을 수월하게 하도록 수정한다.
그리고 검사하는 partial array를 select로 명명하고 set을 사용하여 종류의 개수를 센다.
완전 탐색을 통해 모든 element를 하나하나씩 가져와서 select로 만들고 테스트를 돌렸으나 어마어마한 시간이 소요되는 것을 확인하였다.
주어진 배열의 길이가 최대 100,000이니까 어쩌면 당연히 시간초과가 발생.
2차 시도 - 투포인터, set 활용
결과: 시간 초과
def solution(gems):
answer = []
ngems = [0] + gems
kinds = set(gems)
need_count = len(kinds)
min_length = 100000
left = 1
right = 1
while left < len(ngems) and right < len(ngems):
select = ngems[left:right + 1]
if len(set(select)) == need_count:
length = right - left + 1
if length < min_length:
min_length = length
answer = [left, right]
left += 1
else:
right += 1
return answer
모든 보석들을 탐색하는 것은 상당한 시간이 걸리므로 투포인터 알고리즘을 적용하여 시간을 어느 정도 줄일 수 있었다.
하지만 여전히 효율성 테스트에서는 시간초과가 발생했다. 즉, 이것이 베스트 솔루션은 아니라는 얘기다.
해당 문제의 원인이 무엇인지 곰곰히 생각해보다가 매 루프마다 존재하는 set(select)가 문제가 되는 게 아닌가 해서 면밀히 조사해봤다.
아니나 다를까 set()을 사용하면 해당 함수에 들어가는 배열의 개수만큼 시간이 소요된다. 즉 모든 루프에서 set을 만들기 위한 연산이 일어나고 이것이 시간을 많이 소요하므로 효율성 테스트를 실패하게 하는 원인인 것이다.
set()를 매 루프마다 사용하면 시간초과가 발생하므로 set()는 한 번만 사용해야 한다.
그럼 set()는 한 번만 사용하고 그 후 element가 변경될 때마다 add(), remove()를 사용할까?
하지만 set()를 한 번만 사용하게 되면 문제가 발생하는게, 투 포인터에 의해 select라는 조각배열에 담기는 값이 변경되면 set 집합을 수정할 수 없다는 것이다.
물론, set에서는 해당 element를 제거하는 메서드 remove()가 제공되지만, 문제는 set는 select에 중복된 보석이 있을 지라도 한 종류로 취급하기 때문에 투포인터의 left가 해당 보석을 하나 제외할 때 set에서 하나를 제외하면, 중복되는 다른 보석들도 다 같이 제외해버리는 꼴이 되는 것이다.
그러므로 set를 사용하는 것에는 한계가 있다. 현재 모은 보석의 종류의 개수를 알 수 있으면서도, 각 종류 별 보석 개수를 셀 수 도 있어야 한다.
종류와 개수를 동시에 처리한다 -> 딕셔너리를 사용할 수 밖에 없다.
3차 시도 - 딕셔너리 활용
결과: 성공
def solution(gems):
answer = []
ngems = [0] + gems
kinds = set(gems)
need_count = len(kinds)
min_length = 100000
dic = {gems[0]:1}
left = 1
right = 1
while left < len(ngems) and right < len(ngems):
if len(dic) == need_count:
length = right - left + 1
if length < min_length:
min_length = length
answer = [left, right]
if dic[ngems[left]] == 1:
del dic[ngems[left]]
else:
dic[ngems[left]] -= 1
left += 1
else:
right += 1
if right == len(ngems):
break
if ngems[right] in dic:
dic[ngems[right]] += 1
else:
dic[ngems[right]] = 1
return answer
주의할점은 딕셔너리에서 해당 보석을 전부 제거해야 한다면 del이라는 함수를 사용해야한다.
딕셔너리는 최초에 선언된 후 값을 넣고 쓰기만 하면 되기 때문에 시간복잡도가 O(1)로 시간이 크게 소요되지 않는다.
len(dic)를 사용하면 현재 검사하는 partial array에 속해있는 보석의 종류의 개수를 계산할 수 있고 이는 매번 set()을 선언하여 사용하는 것보다 시간을 훨씬 아낄 수 있다.
그렇기 때문에 해당 코드는 효율성 테스트를 통과할 수 있었다.
결론
투포인터 + 해시 알고리즘
그러므로 이 문제는 투 포인터 문제인 동시에 해시 문제이기도 한 것이다. 많은 글들이 이 문제의 카테고리를 투 포인터로만 분류하던데, 본인처럼 투포인터만 고려하여 문제를 풀면 이와같이 효율성 테스트에서 실패할 수도 있다.
'Algorithm' 카테고리의 다른 글
| [프로그래머스] 시소 짝꿍 문제. 배열이 길다면 해시를 생각해보자. (0) | 2024.02.25 |
|---|---|
| max(), min()은 언제 어떻게 사용하는 게 좋을까? (0) | 2023.09.15 |