징검다리 건너기 (64062번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 징검다리 건너기 (64062번)

자료구조&알고리즘 : 우선순위 큐 (Priority Queue)

난이도 : Lv 3

 

---

 

2019 카카오 개발자 겨울 인턴십 기출문제이다.

 

처음에 파라메트릭 서치 (Parametric Search) 로 풀어봤는데,

효율성에서 5개 케이스 정도가 시간 초과가 발생했다.

 

'''
Parametric Search
효율성 시간 초과
'''

class SteppingStones():
    def __init__(self, stones, k):
        self.k, self.stones = k, stones
        self._param_search()
    
    
    def _param_search(self):
        s, e = 1, 200000000
        while s < e:
            m = (s+e)>>1
            if self._is_poss(m):
                s = m+1
            else:
                e = m
        self.answer = e-1
        
    
    def _is_poss(self, x):
        cnt = maxy = 0
        for stone in self.stones:
            if stone < x:
                cnt += 1
            else:
                maxy = max(cnt, maxy)
                cnt = 0
        maxy = max(cnt, maxy)
        return True if maxy < self.k else False

        
def solution(stones, k):
    step_stones = SteppingStones(stones, k)
    return step_stones.answer

 

 

---

 

 

아래의 우선순위 큐를 활용한 방법으로 구현했더니

시간 초과 없이 통과할 수 있었다.

 

 

''' 우선순위 큐 '''


import sys
from heapq import heapify, heappop, heappush


class SteppingStones():
    def __init__(self, stones, k):
        answer = sys.maxsize
        stones = [(-stone, i) for i, stone in enumerate(stones)]
        pq = stones[:(k-1)]
        heapify(pq)
        for i in range(k-1, len(stones)):
            heappush(pq, stones[i])
            while pq and pq[0][1] + k <= i:
                heappop(pq)
            answer = min(answer, -pq[0][0])
        self.answer = answer


def solution(stones, k):
    step_stones = SteppingStones(stones, k)
    return step_stones.answer

 

 

① stones를 (-value, index) 형태로 저장한다.

value에 마이너스를 곱하는 이유는, 우선순위 큐에서 최대값을 꺼내오기 위함이다.

 

 

 

② stone의 값을 (-value, index) 형태로 하나씩 넣어주면서,

k 길이의 연속된 배열에서 가장 큰 값을 가져온다.

 

만약 가져온 가장 큰 값의 index가, 현재 index보다 k 이상으로 더 작다면

해당 값은 현재 k 길이의 연속 배열 안에 있지 않으므로,

현재 배열 내부의 index 값을 가진 가장 큰 값이 나올 때까지, 우선순위 큐에서 계속 꺼내준다.

while pq and pq[0][1] + k <= i:
    heappop(pq)

 

만약 우선순위 큐에서 갖아 큰 value의 index 값이 현재 배열 안에 있다면,

그 값이 현재 배열에서의 최대값이 된다.

그 값을 answer와 비교해서, 더 작은 값을 answer에 할당한다.

answer = min(answer, -pq[0][0])

 

 

 

③ 위의 과정을 모두 진행하고 나면, answer 값을 반환한다.

( answer 값은 모든 k 길이의 연속 배열의 최대값들의 최솟값이다.

즉, 징검다리를 건널 수 있는 최대 인원 수이다.)