[알고리즘/파이썬] 프로그래머스 - 징검다리 건너기

문제

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

프로그래머스

 

풀이

처음 시도

그냥 while문 안에서 for문 돌면서 -1씩 해주고 연속된 0이 k만큼 되면 못 건너는걸로 판단하고 break. ㅋㅋ ㅠㅠ 당연히 시간 초과. 징검다리 최고 숫자가 무려 200,000,000이고 징검다리도 200,000개이므로... 만약 죄다 200,000,000이 써져 있는 200,000개의 징검다리가 있다고 치면 내 코드는 그냥 쓰레기 코드가 된다 :)

def solution(stones, k):
    answer = 0
    
    
    while True:
        flag = 0
        for i in range(len(stones)):
            if stones[i]>0:
                stones[i] -= 1
                flag = 0
            else:
                flag += 1
                
            if flag == k:
                break          
        if flag == k:
            break
        answer += 1
            
    return answer

이게 바로 그 쓰레기 코드 ㅎㅎ

 

 

두번째시도

자.. 그럼 다시 이성적으로 생각해보자

아 다시 보니까 k만큼 분리해서 봤을 때의 최댓값들 중 최솟값이 answer이 되더라.

예를 들어서 

5 4 3 2 1 이라는 징검다리가 있고, k가 2라고 해보자.

한 번 건너면 4 3 2 1 0이 되고 두 번 건너면 3 2 1 0 0이 된다. 그럼 이제 못 건너는 상태가 되니까 2명이 건널 수 있는 건데

이 배열을 2개씩 슬라이딩해서 봤을 때 5,4 에서 최댓값 5/ 4,3 에서 최댓값 4/ 3,2에서 최댓값 3/ 2,1에서 최댓값 2

해서 이 5,4,3,2 중 최솟값인 2가 우리가 원하는 정답이 되는거다.

 

이거까진 ok 혼자 잘 생각해냈다.

그래서 코드를 짰는데 ㅋㅋ max함수 없이 어떻게 짜야할지 모르겠고... heap을 사용해서 최댓값을 뽑아야 할 것 같은데 그러면 이 아이를 어떻게 다시 넣고 뺄 지도 모르겠고 ㅠㅠ 그래서 결국 또 시간 초과 코드를 짜고 만다... :)

from collections import deque
def solution(stones, k):
    answer = 1e9
    q = deque()
    
    for s in stones:
        q.append(s)
        if len(q) == k:
            max_num = max(q)
            if max_num < answer:
                answer = max_num
            q.popleft()
    
            
    return answer

효율성에서는 여전히 0점이었지만 ^^ 그래도 첫 번째 코드보다 시간이 훨~씬 많이 줄어들었다.

 

정답 코드

자 그럼 이제 내가 싸놓은 이상한 코드 말고 정답 코드를 봐보자... 역시 heapq를 사용해야 했더라. 내가 다시 넣고 빼는걸 고민했는데 heap을 만들 때 Index도 함께 저장해둔다.

import heapq
from math import inf

def solution(stones, k):
    n = len(stones)

    # 최대 힙 방식으로 각 구간의 최댓값을 구할 것이다.
    queue = []
    answer = inf

    # 먼저 0부터 k - 2 까지 최대 힙에 인덱스와 함께 넣자.
    for i in range(k - 1):
        heapq.heappush(queue, [-stones[i], i])

    # k - 1부턴 하나씩 최대 힙에 넣자.
    # 최대 힙의 맨 앞의 인덱스가 i - k + 1보다 작다면 구간을 벗어난 원소
    # 구간을 벗어난 원소를 전부 pop
    for i in range(k - 1, n):
        heapq.heappush(queue, [-stones[i], i])
        while queue[0][1] < i - k + 1:
            heapq.heappop(queue)
        answer = min(answer, -queue[0][0]) # 답은 각 구간의 최댓값들의 최솟값

    return answer

 

최대힙으로 구현을 해놨기 때문에 queue[0][0]을 뽑으면 현재 윈도우에서의 최대값이 나오고, queue[0][1]을 뽑으면 현재 윈도우에서의 최대값의 인덱스가 나온다.

 

만약 1 2 5 4 3 2 이런 아이들이 있고 k가 3이라고 한다면 처음에 queue에는 1 2 5가 들어가고, 최대힙이기 때문에 queue[0][0]은 5(-5), queue[0][1]은 2일 것이다.

다음엔 4가 들어갈텐데 어차피 가장 큰 값이 5고 4와 5의 인덱스 차이는 1이기 때문에(k보다 크지 않기 때문에 / 같은 윈도우에 속하기 때문에) 그냥 진행하고, 그 다음에 3이 들어갈 때도 여전히 queue에서 가장 큰 값이 5고, 5와 3의 인덱스 차이가 2이기 때문에 (k보다 크지 않기 때문에 / 같은 윈도우에 속하기 때문에) 그냥 진행한다. 이런 식으로 진행하면서 가장 큰 값과 현재 값이 인덱스 차이가 k이상 일 때(같은 윈도우에 속하지 않을 때)에는 heappop을 통해 없애주는 거다.

 

 

 

완전한 답을 도출하지 못한건 아쉽지만, k씩 묶어서 최댓값 중 최솟값을 뽑는것...이라는 생각을 한 것만으로도 내 스스로가 대견 ^ __ ^ . . . .