보기엔 쉬워보이나 제대로 풀려면 two pointer 알고리즘이라는 방법을 사용해야 하는 까다로운 문제였다.
일단 문제를 봤을 때 접근할 수 있는 가장 단순한 방법은 가장 작은 구간 크기를 K로 시작해 배열 안에서 window sliding
을 사용하여 1씩 이동시키면서 찾는 방법이다. K 크기의 구간에 만족하는 케이스가 없으면 구간의 크기를 1씩 늘려준다.
하지만 이 방법은 조건에서 배열의 크기가 최대 100,000으로 주어졌기 때문에 시간복잡도 으로 효율성 테스트를 통과하지 못한다.
그래서 생각한 방법이 위 방법에서 구간의 크기를 로 놓고 이 값을 이분탐색으로 찾는 방법이었다. 이 방법을 사용하면 으로 효율성 테스트를 통과할 수 있다고 생각했는데, 앞의 방법보다 시간이 줄긴했지만 효율성 테스트를 통과하지 못했다.
def solution(gems):
answer = []
# init settings
unique_gems = {}
for gem in gems:
if not unique_gems.get(gem):
unique_gems[gem] = 0
# binary search. target is section length
N = len(gems)
K = len(unique_gems)
l, r = K, N
start, end = 0, 0
while l <= r:
mid = (l + r) // 2
flag = 0
for i in range(N-mid+1):
cnt = 0
tmp = {k:v for k,v in unique_gems.items()}
for ele in gems[i:i+mid]:
if not tmp[ele]:
tmp[ele] = 1
cnt += 1
if cnt == K:
flag = 1
start, end = i+1, i+mid
break
if flag:
res = mid
if mid == K:
break
else:
r = mid - 1
else:
l = mid + 1
answer = [start, end]
return answer
문제를 풀기위해 여러 고민을 해보았지만 도저히 만에 푸는 방법이 떠오르지 않아 다른 사람들의 풀이를 참고하였고, two pointer 알고리즘이라는 것을 알게되었다.
two pointer 알고리즘의 개념은 단순하다.
시작과 끝점인 start
, end
두 개의 포인터를 사용하여 1차원 배열 안에서 원하는 형태를 얻는 것이다.
문제를 해결하기 위해 중요한 점은 start
와 end
포인터를 어떻게 조작할지에 대한 기준을 세우는 것이다. 여기선 가장 작은 구간의 크기를 찾는 것이 중요하기 때문에 이를 두 포인터를 조작하는 기준으로 삼았다.
먼저 end
포인터를 적어도 한 개의 보석을 포함하는 구간을 완성할 때까지 증가시켜주고, 구간이 완성되면 start
포인터를 증가시켜주면서 가장 작은 구간의 크기를 찾았다. 이 작업을 두 포인터가 배열의 끝에 도달할 때까지 반복해주면 , 즉 만에 답을 구할 수 있다.
def solution(gems):
answer = []
# 1. init settings
unique_gems = {}
for gem in gems:
if not unique_gems.get(gem):
unique_gems[gem] = 0
# 2. two pointer algorithm
N = len(gems)
K = len(unique_gems)
start, end = 0, 0
cnt = 0
res = []
while start < N and end <= N:
if cnt == K:
res.append([end - start, start+1, end])
unique_gems[gems[start]] -= 1
if not unique_gems[gems[start]]:
cnt -= 1
start += 1
else:
if end < N:
if not unique_gems[gems[end]]:
cnt += 1
unique_gems[gems[end]] += 1
end += 1
else:
unique_gems[gems[start]] -= 1
if not unique_gems[gems[start]]:
cnt -= 1
start += 1
answer = sorted(res)
answer = answer[0][1:]
return answer
마지막에 정렬을 해주는게 아니라 애초에 res
를 최소 힙으로 구현했으면 더 빨랐을 것 같지만, 귀찮아서 여기까지만...