카카오 2019 겨울인턴십 - 불량 사용자

https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

 

처음 시도했던 방법

def solution(stones, k):
    answer = 0
    ans = stones[0:k]
    compare = stones[0:k]
    
    for s in range(0, len(stones)-k):

        cpr = compare.pop(0)
        compare.append(stones[s+k])

        if max(ans) > max(compare):
            ans = compare
            answer = max(compare)
            
    return answer

 

처음에는 맨 처음 0부터 k까지의 숫자를 하나의 배열로 지정한 뒤, 배열에서 0번째 칸은 버리고 s+k번째 칸을 추가하는 걸 반복하며 최대값이 가장 작게 나오는 배열의 최대값을 구하는 방법을 생각했다. 정확도 테스트는 통과하지만 효율성 테스트를 통과할 수 없었다.

 

선형구조 탐색시간을 줄이는 방법은

• 해시 : 해싱 함수를 거쳐 탐색 시간을 줄일 수 있음
• 이분 탐색 : 경우의 수를 1/2씩 줄여나가며 탐색 시간을 줄일 수 있음

이 방법은 징검다리의 숫자가 그렇게 크지 않은 경우는 위와 같은 방법이 더 빠를 수 있지만, 징검다리의 숫자가 최대 2억이므로 절반씩 경우의 수를 줄여나가며 탐색할 수 있는 이분 탐색이 효과적이다.

 

수정한 방법

def solution(stones, k):
    start, end = 1, 200000000

    while start <= end:
        temp = stones[:]
        mid = (start + end) // 2

        for t in range(len(temp)):
            temp[t] -= mid

        count = 0
        for i in range(len(temp)):
            if temp[i] <= 0:
                count += 1
            else:
                count = 0

            if count >= k:
                end = mid - 1
                break
        else:
            start = mid + 1

    return start

 다음과 같은 과정을 거치며 이분 탐색을 진행한다.

 

1. stones에서 각 원소에서 답으로 가정할 mid값을 뺀 배열 temp를 만든다.
2. 3번 연속 0 이하의 값이 나오면 (0 이하인 경우 건널 수 없게 됨) 너무 큰 값을 뺐다고 판단하고 1 ~ 2억이라는 경우의 수를 왼쪽으로 옮긴다 ( 1 ~ 200000000 의 중간값에서 1 ~ 100000001의 중간값으로 mid값이 바뀌게 된다.)
3. start가 end를 만날때까지 반복하다가 종료한다.