징검다리 건너기

 

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

프로그래머스

문제설명:

돌의 내구도 가 주어지고 한번에 건널수 있는 최대값이 주어진다. 최대 몇명이 건너갈 수 있는가

 

소요시간:

50분

난이도 3

 

1차 코딩: (15분)

def solution(stones, k):
	q = []
	for i in range(len(stones)-k+1):
		q.append(max(stones[i:i+k]))
	return min(q)

저는 이문제의 대한 알고리즘을 주어진 구간의 대해서 슬라이딩 하면서 그안에서 최대값들의 중에서 최소값을 구하는 방식으로 구조를 짰습니다. 왜냐하면 k개 만큼 건널수 있고, 그렇다면 k개의 구간중 가장 큰값이 그 구간을 건널수 있는 가장큰 방법일 것이기 때문에 모든 구간에대한 그값들중 가장 작은값이 전체를 건널수 있는 값이라고 생각했습니다.

그래서 위와 같이 코딩을 했고, 정확성 테스트에선 모두 맞췄지만 효율성테스트는 모두 실패했기 때문에 다시 코딩했습니다.

 

2차코딩:

import heapq as hp
def solution(stones, k):
	stones = list(map(lambda x : -1*x, stones))
	A = stones[0:k-1]
	hp.heapify(A)
	B = []
	m = -int(1e9)
	for i in range(k-1,len(stones)):
		#A는 특정 구간의 최대값을 구하기위함
		#i 번째를 넣고 최대값을 뽑음
		hp.heappush(A,stones[i])
		#구간들의 최대값들 중에서 최소값을 구함
		if m < A[0]:
			m = A[0]
		#B에 없어질 후보를 넣음
		hp.heappush(B,stones[i - (k-1)])	

		#없어져야한다면 없애자
		while B and A[0]==B[0]:
			hp.heappop(A)
			hp.heappop(B)
		
	return -1*m

2차코딩에 대해서는 효율성을 위해, heap구조를 사용하였고 특정 구간에 들어갈때마다 heap에 넣어주는것은 문제가 되지않지만 빼는것이 문제였습니다. 우선순위큐에서 임의 요소를 삭제하는것은 안되기때문에, 

https://panty.run/pq-del-elem/

다음 블로그에서 내용을 참고했습니다.

 

만약 수의 들어가는 범위가 작다면 카운팅 배열을 새로 만든다음에, arr[7] +=1 과 같이 개수를 기록해놓고 top이 기록된요소였다면 지우는방법이 있지만 시간도 오래걸리고 배열의 선언도 추가로 해줘야하기 때문에, 

다음과같이 지울것을 기록하는것입니다. 문제에서 예를들어 A(왼쪽)에 차곡차곡 넣어 최대를 확인하고 맨왼쪽것을 빼야될때, 맨왼쪽이 최대가 아니라면 어차피 그다음 구간에서 최대를 구하는것에 영향을 주지 않기 때문에, B(오른쪽)에 기록을 해두었다가 만약 A에서 맨왼쪽에 해당하는 값을 뺐는데, 그것이 최대였다면 빼주는것 입니다. 이때 이전까지 빼줬어야 하는것들이 쌓여있기 때문에 while문을 통하여 빼주어야했을 값들도 모두 빼줍니다.

 

다른사람 풀이:

def solution(stones, k):
    left = 0
    right = max(stones)+1

    def compare(mid):
        return any( len(i)>=k for i in "".join(["T" if i>mid else "F" for i in stones]).split("T"))

    while left<right:
        mid = (left+right)//2
        if compare(mid):
            right = mid
        else:
            left = mid + 1

    return right

쉽게 말해 중간값을 계속 생각해 만약 mid 가 3이었다면 3보다 높은값들만 이어서 그 이어진것 간의 최대길이가 3미만이라면 건널수 있다라고 판단하는 로직입니다.