[kakao 2019 internship]징검다리 건너기

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

코딩테스트 연습 - 징검다리 건너기

[실수 1]

처음에 가장 간단하게 생각했던건

징검다리를 sorted 하고 check하는 방법.

이건 시간 초과가 났다.

 

list--> set 으로 바꾸는 것 자체가  O(n)

그걸 sorted 하는 것이 O(nlogn)

그 한줄로 이미 O(n^2logn)이 되버렸다.ㅎ

def solution(stones, k):
    s=sorted(list(set(stones)))
    q=[]
    answer=0
    for i in s:
        if not check(i,stones,k):
            answer=i
            break

    return answer

[실수 2]

그으래서 생각했던건 min heap으로 진행. -->이것역시 시간초과

이것도 마찬가지로 heapify가 O(nlogn)의 시간복잡도를 갖게되기때문에

while문에서 O(n^2longn)의 복잡도를 갖게된다.

from heapq import heappush,heappop
def solution(stones, k):
	q=[]
	for i in stones:
    	heappush(q,i)
    answer=0
    while True:
    	cur_val=heappop(q)
        while cur_val==q[0]:
        	heappop(q)
		check(i,stones,k)
    return answer

 

[해설]

이분탐색으로 1~200,000,000 에서 적합한 수를 정한다.

이분탐색이니, nlogn 의 복잡도를 갖는다.

def check(val,stones, k):
    ck = 0
    for i in stones:
        if i - val <= 0:
            ck += 1
        else:
            ck = 0
        if ck >= k:
            return True
    return False

def solution(stones, k):
    min_v,max_v=1,200000000
    while max_v-1>min_v:
        print(max_v,min_v)
        mid_v=(min_v+max_v)//2
        if check(mid_v,stones,k):
            max_v=mid_v
        else:
            min_v=mid_v


    return max_v

 

이분탐색 문제를 좀더 풀어봐야겟다