프로그래머스 징검다리 건너기 (2019 카카오 개발자 겨울 인턴쉽, 이분탐색)

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

입출력 예

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

입출력 예 설명

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

풀이

• 이 문제는 이건 어디가 빵꾸나는지 알면 되는거네?
  • 이것도 슬라이딩 윈도우인가?
• 간격이... k 간격 범위에서 max값을 슬라이딩하면서 갱신하고
  • 마지막에 제일 작은 max를 저장하고 있다가 마지막에 리턴...
• k만큼 빵꾸나면 그 때까지 루프 돈 횟수를 리턴하면 되는 문제.
  • ...는 시간 초과

import collections

def solution(stones, k):
    min_stones = 200000001
    kstonebridge = {}
    kstonebridge = collections.Counter(stones[0:k])
    # print(kstonebridge)
    for i in range(k, len(stones)):
        try:
            kstonebridge[stones[i]] += 1
        except:
            kstonebridge[stones[i]] = 1
        kstonebridge[stones[i-k]] -= 1
        if kstonebridge[stones[i-k]] == 0:
            del kstonebridge[stones[i-k]]
        if min_stones > max(kstonebridge):
            min_stones = max(kstonebridge)
        
    return min_stones
    
정확성  테스트
테스트 1 〉	실패 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.05ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (0.12ms, 10.1MB)
테스트 5 〉	통과 (0.13ms, 10.1MB)
테스트 6 〉	통과 (0.64ms, 10.2MB)
테스트 7 〉	통과 (2.58ms, 10.3MB)
테스트 8 〉	통과 (3.22ms, 10.2MB)
테스트 9 〉	통과 (2.44ms, 10.2MB)
테스트 10 〉	통과 (0.14ms, 10.1MB)
테스트 11 〉	통과 (0.04ms, 10.2MB)
테스트 12 〉	통과 (0.14ms, 10.3MB)
테스트 13 〉	통과 (0.25ms, 10.3MB)
테스트 14 〉	통과 (0.78ms, 10MB)
테스트 15 〉	통과 (2.60ms, 10.4MB)
테스트 16 〉	통과 (3.58ms, 10.1MB)
테스트 17 〉	통과 (3.30ms, 10.1MB)
테스트 18 〉	통과 (0.07ms, 10.1MB)
테스트 19 〉	통과 (0.08ms, 10MB)
테스트 20 〉	통과 (0.13ms, 10.1MB)
테스트 21 〉	통과 (0.63ms, 10.3MB)
테스트 22 〉	통과 (1.30ms, 10.3MB)
테스트 23 〉	통과 (1.77ms, 10.1MB)
테스트 24 〉	통과 (2.05ms, 10.1MB)
테스트 25 〉	통과 (0.06ms, 10.1MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)

• max 함수 2번 써서 그런가? 아무리 뜯어고쳐도 안된다. ㅋㅋㅋ
  • 이분탐색으로 풀으라고 했으니 이분탐색으로 풀어야겠다.

import collections

def solution(stones, k):
    if k == 1:
        return min(stones)
    
    kstonebridge_set = set(stones[0:k])
    kstonebridge = {}
    kstonebridge = collections.Counter(stones[0:k])
    max_stone = max(kstonebridge)
    min_stone = max_stone
    
    for i in range(k, len(stones)):
        next_stone = stones[i]
        kstonebridge_set.add(next_stone)
        try:
            kstonebridge[next_stone] += 1
        except:
            kstonebridge[next_stone] = 1
        
        prev_stone = stones[i-k]
        kstonebridge[prev_stone] -= 1
        if kstonebridge[prev_stone] == 0:
            try:
                kstonebridge_set.remove(prev_stone)
                max_stone = max(kstonebridge_set)
                if min_stone > max_stone:
                    min_stone = max_stone
            except:
                if min_stone > max_stone:
                    min_stone = max_stone
        
    return min_stone

• 이분탐색 재귀 호출...
  • 정답을 찍는 방식... ㅡ.ㅡ;;;
    • 내가 제일 안쓰는 방법인데, 답이 1개 일 때는... 써야하는구나!

import sys
sys.setrecursionlimit(10**5)

def solution(stones, k):
    low = 1
    high = max(stones)
    
    def binSearch(low, high):
        mid = (high-low)//2
        if mid == 0:
            return high
        mid += low
        cnt_stone = 0
        for stone in stones:
            if stone - mid <= 0:
                cnt_stone += 1
            else:
                cnt_stone = 0
            if cnt_stone == k:
                break
        if cnt_stone == k:
            return binSearch(low, mid)
        else:
            return binSearch(mid, high)
        
    return binSearch(low, high)

• 큼... 이게 슬라이딩 지렁이로 하려고 했던 것 보다 더 빠르네?

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.03ms, 10.1MB)
테스트 5 〉	통과 (0.05ms, 10.3MB)
테스트 6 〉	통과 (0.66ms, 10.3MB)
테스트 7 〉	통과 (0.58ms, 10.3MB)
테스트 8 〉	통과 (1.28ms, 10.1MB)
테스트 9 〉	통과 (1.21ms, 10.2MB)
테스트 10 〉	통과 (0.02ms, 10MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.03ms, 10.2MB)
테스트 13 〉	통과 (0.06ms, 10MB)
테스트 14 〉	통과 (0.47ms, 9.99MB)
테스트 15 〉	통과 (1.25ms, 10.1MB)
테스트 16 〉	통과 (0.80ms, 10.2MB)
테스트 17 〉	통과 (0.85ms, 10.2MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.05ms, 10.1MB)
테스트 20 〉	통과 (0.09ms, 10.2MB)
테스트 21 〉	통과 (0.46ms, 10.1MB)
테스트 22 〉	통과 (1.13ms, 10MB)
테스트 23 〉	통과 (0.91ms, 10.3MB)
테스트 24 〉	통과 (1.08ms, 10.3MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (251.37ms, 18.6MB)
테스트 2 〉	통과 (320.59ms, 18.6MB)
테스트 3 〉	통과 (347.97ms, 18.6MB)
테스트 4 〉	통과 (176.48ms, 18.5MB)
테스트 5 〉	통과 (211.01ms, 18.5MB)
테스트 6 〉	통과 (238.14ms, 18.5MB)
테스트 7 〉	통과 (340.32ms, 18.6MB)
테스트 8 〉	통과 (398.81ms, 18.6MB)
테스트 9 〉	통과 (388.43ms, 18.6MB)
테스트 10 〉	통과 (351.45ms, 18.6MB)
테스트 11 〉	통과 (361.99ms, 18.6MB)
테스트 12 〉	통과 (348.21ms, 18.5MB)
테스트 13 〉	통과 (281.42ms, 18.5MB)
테스트 14 〉	통과 (203.89ms, 18.6MB)

• 힙큐를 썼네? 지렸다.

import heapq

def solution(stones, k):

    heap = []
    for i in range(k):
        #구간합의 최댓값을 계속 유지해야해서 -로 집어넣어야함
        heapq.heappush(heap, [-stones[i],i])

    answer = 10**9
    i = k - 1
    while i < len(stones):
        heapq.heappush(heap,[-stones[i],i])

        while heap[0][1] < i - k + 1:
            heapq.heappop(heap)
        i += 1
        answer = min(answer, -heap[0][0])

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 9.99MB)
테스트 4 〉	통과 (0.06ms, 10.3MB)
테스트 5 〉	통과 (0.14ms, 10.1MB)
테스트 6 〉	통과 (0.72ms, 10.3MB)
테스트 7 〉	통과 (0.76ms, 10.2MB)
테스트 8 〉	통과 (0.70ms, 10.1MB)
테스트 9 〉	통과 (1.03ms, 10.2MB)
테스트 10 〉	통과 (0.16ms, 10.3MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (0.04ms, 9.93MB)
테스트 13 〉	통과 (0.08ms, 10.1MB)
테스트 14 〉	통과 (0.38ms, 10.2MB)
테스트 15 〉	통과 (0.82ms, 10.2MB)
테스트 16 〉	통과 (1.20ms, 10.3MB)
테스트 17 〉	통과 (1.20ms, 10.3MB)
테스트 18 〉	통과 (0.02ms, 10.1MB)
테스트 19 〉	통과 (0.07ms, 10.4MB)
테스트 20 〉	통과 (0.12ms, 10.1MB)
테스트 21 〉	통과 (0.77ms, 10.2MB)
테스트 22 〉	통과 (0.93ms, 10.2MB)
테스트 23 〉	통과 (0.85ms, 10.2MB)
테스트 24 〉	통과 (0.93ms, 10.4MB)
테스트 25 〉	통과 (0.03ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (172.78ms, 48.6MB)
테스트 2 〉	통과 (172.36ms, 48.7MB)
테스트 3 〉	통과 (185.38ms, 48.7MB)
테스트 4 〉	통과 (337.15ms, 22.9MB)
테스트 5 〉	통과 (359.72ms, 25.2MB)
테스트 6 〉	통과 (307.15ms, 24MB)
테스트 7 〉	통과 (163.12ms, 48.6MB)
테스트 8 〉	통과 (144.67ms, 48.6MB)
테스트 9 〉	통과 (164.22ms, 48.5MB)
테스트 10 〉	통과 (148.15ms, 48.6MB)
테스트 11 〉	통과 (146.11ms, 48.6MB)
테스트 12 〉	통과 (146.51ms, 48.6MB)
테스트 13 〉	통과 (297.41ms, 24.9MB)
테스트 14 〉	통과 (220.32ms, 48.6MB)

• 와... 딕셔너리도 되는 거였네. 내가 멍청했던 걸로

def solution(stones, k):

    nums_pos = dict()
    for pos, stone in enumerate(stones):
        if stone not in nums_pos:
            nums_pos[stone] = []
        nums_pos[stone].append(pos + 1)
    dist = [[1, i - 1, i + 1] for i in range(len(stones) + 2)]

    ans = 0
    for num in sorted(nums_pos):
        ans = num            
        for cur in nums_pos[num]:
            d, prev, next = dist[cur]
            dist[prev][0] += d
            dist[prev][2], dist[next][1] = next, prev
            if dist[prev][0] > k:
                return ans

    return ans
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.03ms, 10.1MB)
테스트 5 〉	통과 (0.04ms, 10.2MB)
테스트 6 〉	통과 (0.56ms, 10.1MB)
테스트 7 〉	통과 (1.28ms, 10.2MB)
테스트 8 〉	통과 (1.34ms, 10.3MB)
테스트 9 〉	통과 (0.79ms, 10.1MB)
테스트 10 〉	통과 (0.04ms, 10.2MB)
테스트 11 〉	통과 (0.02ms, 10.1MB)
테스트 12 〉	통과 (0.05ms, 10.2MB)
테스트 13 〉	통과 (0.06ms, 10.1MB)
테스트 14 〉	통과 (0.35ms, 10.3MB)
테스트 15 〉	통과 (0.83ms, 10.3MB)
테스트 16 〉	통과 (0.87ms, 10.3MB)
테스트 17 〉	통과 (1.58ms, 10.3MB)
테스트 18 〉	통과 (0.02ms, 10.1MB)
테스트 19 〉	통과 (0.03ms, 10.2MB)
테스트 20 〉	통과 (0.06ms, 10.2MB)
테스트 21 〉	통과 (0.31ms, 10.3MB)
테스트 22 〉	통과 (0.70ms, 10.2MB)
테스트 23 〉	통과 (0.76ms, 10.3MB)
테스트 24 〉	통과 (0.79ms, 10.3MB)
테스트 25 〉	통과 (0.03ms, 10MB)
효율성  테스트
테스트 1 〉	통과 (505.87ms, 87.1MB)
테스트 2 〉	통과 (555.50ms, 87.1MB)
테스트 3 〉	통과 (472.18ms, 75.4MB)
테스트 4 〉	통과 (209.26ms, 75.5MB)
테스트 5 〉	통과 (243.16ms, 75.4MB)
테스트 6 〉	통과 (230.21ms, 75.6MB)
테스트 7 〉	통과 (544.13ms, 87.1MB)
테스트 8 〉	통과 (510.48ms, 87.2MB)
테스트 9 〉	통과 (499.16ms, 87.1MB)
테스트 10 〉	통과 (451.80ms, 87.1MB)
테스트 11 〉	통과 (420.42ms, 74.2MB)
테스트 12 〉	통과 (356.15ms, 73.2MB)
테스트 13 〉	통과 (192.78ms, 86.2MB)
테스트 14 〉	통과 (214.57ms, 86.3MB)