보석 쇼핑

이현빈·2021년 7월 22일
0

문제

프로그래머스 보석 쇼핑

문제풀이

보기엔 쉬워보이나 제대로 풀려면 two pointer 알고리즘이라는 방법을 사용해야 하는 까다로운 문제였다.

실패한 방법

일단 문제를 봤을 때 접근할 수 있는 가장 단순한 방법은 가장 작은 구간 크기를 K로 시작해 배열 안에서 window sliding을 사용하여 1씩 이동시키면서 찾는 방법이다. K 크기의 구간에 만족하는 케이스가 없으면 구간의 크기를 1씩 늘려준다.
하지만 이 방법은 조건에서 배열의 크기가 최대 100,000으로 주어졌기 때문에 시간복잡도 O(n2)O(n^2)으로 효율성 테스트를 통과하지 못한다.

그래서 생각한 방법이 위 방법에서 구간의 크기를 xx로 놓고 이 xx값을 이분탐색으로 찾는 방법이었다. 이 방법을 사용하면 O(nlogn)O(nlogn)으로 효율성 테스트를 통과할 수 있다고 생각했는데, 앞의 방법보다 시간이 줄긴했지만 효율성 테스트를 통과하지 못했다.

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

문제를 풀기위해 여러 고민을 해보았지만 도저히 O(n)O(n)만에 푸는 방법이 떠오르지 않아 다른 사람들의 풀이를 참고하였고, two pointer 알고리즘이라는 것을 알게되었다.

성공한 방법

two pointer 알고리즘의 개념은 단순하다.
시작과 끝점인 start, end 두 개의 포인터를 사용하여 1차원 배열 안에서 원하는 형태를 얻는 것이다.

문제를 해결하기 위해 중요한 점은 startend 포인터를 어떻게 조작할지에 대한 기준을 세우는 것이다. 여기선 가장 작은 구간의 크기를 찾는 것이 중요하기 때문에 이를 두 포인터를 조작하는 기준으로 삼았다.

먼저 end 포인터를 적어도 한 개의 보석을 포함하는 구간을 완성할 때까지 증가시켜주고, 구간이 완성되면 start 포인터를 증가시켜주면서 가장 작은 구간의 크기를 찾았다. 이 작업을 두 포인터가 배열의 끝에 도달할 때까지 반복해주면 O(2n)O(2n), 즉 O(n)O(n)만에 답을 구할 수 있다.

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를 최소 힙으로 구현했으면 더 빨랐을 것 같지만, 귀찮아서 여기까지만...

profile
익숙해질때까지 한걸음씩

0개의 댓글