[13회차]

Programmers Level.3 입국심사

def solution(n, times):
    start = 0
    end = max(times) * n
    answer = 0
    while start <= end:
        mid = (start + end) // 2 # 주어진 시간 mid분일 때
        m = 0 # 심사할 수 있는 사람 수
        for time in times:
            m += mid//time
        if m >= n: # 심사 가능한 사람이 n명 이상일 때
            end = mid - 1 # 시간을 덜 줘야함
            answer = mid
        else: # 심사 가능한 사람이 n명보다 적을 때
            start = mid + 1 # 시간을 더 줘야함
    return answer

 - 이분 탐색.

 

 

Programmers Level.3 이중 우선순위 큐

def solution(operations):
    q = []
    for operation in operations:
        a, b = operation.split(' ')
        if a == 'I':
            q.append(int(b))
        if a == 'D' and b == '1' and len(q) > 0:
            q.remove(max(q))
        if a == 'D' and b == '-1' and len(q) > 0:
            q.remove(min(q))
    if len(q) == 0:
        return [0,0]
    else:
        return [max(q), min(q)]

 - 힙을 쓴 풀이가 궁금해서 다른 풀이를 좀 찾아봤다.

import heapq

# 힙에서 원소 뺐으면 다른 힙 초기화하고 다시 넣어줌
def changeHeap(heap):
    h = []
    for num in heap:
        heapq.heappush(h, -num)
    return h

def solution(operations):
    answer = []  # [최댓값, 최솟값]
    minheap = []
    maxheap = []

    for o in operations:
        command, num = o.split(' ')
        num = int(num)
        if command == 'I':
            heapq.heappush(minheap, num)
            heapq.heappush(maxheap, -num)
        elif command == 'D':
            try:
                if num == 1:  # 최댓값 삭제
                    heapq.heappop(maxheap)
                    minheap = changeHeap(maxheap)
                else:  # 최솟값 삭제
                    heapq.heappop(minheap)
                    maxheap = changeHeap(minheap)
            except:
                continue

    if len(maxheap) != 0:
        answer.append(-maxheap[0])
    else:
        answer.append(0)
    if len(minheap) != 0:
        answer.append(minheap[0])
    else:
        answer.append(0)
    return answer

import heapq

def solution(operations):
    h = []

    for i in operations:
        a, b = i.split()
        if a == 'I':
            heapq.heappush(h, int(b))
        else:
            if len(h) > 0:
                if b == '1':
                    h.pop(h.index(heapq.nlargest(1, h)[0]))
                else:
                    heapq.heappop(h)

    if len(h) == 0:
        return [0, 0]
    else:
        return [heapq.nlargest(1, h)[0], h[0]]

 

 

Programmers Level.3 하노이의 탑

def road(n,start,mid,end):
    if n == 1:
        return [[start,end]]
    return road(n-1,start,end,mid) + [[start,end]] + road(n-1,mid,start,end)


def solution(n):
    answer = road(n,1,2,3)
    return answer

 

 

Programmers Level.3 징검다리 건너기

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

 - 틀린 풀이. 돌을 밟으면서 k칸 이상 건너 뛰는 경우에 결과를 return하도록 했는데, 정확성 테스트에서도 몇 개 실패했을 뿐더러 효율성 테스트에서는 최악..

# 이진탐색

def solution(stones, k):
    start = min(stones)
    end = max(stones)
    
    
    def check(stones, k, mid): # mid명일때 건널 수 있는가?
        checking = [0] * len(stones)
        for i in range(len(stones)):
            if stones[i] <= mid:
                if i == 0:
                    checking[i] = 1
                else:
                    checking[i] = checking[i-1] + 1
            if checking[i] == k:
                return True # 건널 수 없다. mid를 낮춰야 함
        return False # 건널 수 있다. mid를 높여야 함
    
    
    while start <= end:
        mid = (start + end) // 2
        if check(stones, k, mid):
            answer = mid
            end = mid -1
        else:
            start = mid +1
    return answer

` - 틀린 풀이 2.    stones배열의 값들이 2억 이하의 값이기 때문에 이진 탐색을 해야 시간 초과가 안 뜰거 같았고 이진탐색의 아이디어를 적용했지만 효율성 테스트에서 일부 시간 초과가 떴다.

 

# 이진탐색

def solution(stones, k):
    start = min(stones)
    end = max(stones)
    
    
    def check(stones, k, mid): # mid명일때 건널 수 있는가?
        cnt = 0
        for stone in stones:
            if stone <= mid:
                cnt += 1
            else:
                cnt = 0
            if cnt == k:
                return True # 건널 수 없다. mid를 낮춰야 함
        return False # 건널 수 있다. mid를 높여야 함
    
    
    while start <= end:
        mid = (start + end) // 2
        if check(stones, k, mid):
            answer = mid
            end = mid -1
        else:
            start = mid +1
    return answer

 - 맞는 풀이. 내 풀이의 어디에서 비효율적임이 나타났을지 고민했다. 징검다리의 연속된 0 개수를 세기 위해 굳이 리스트를 사용할 필요가 없었고 이걸 cnt로 바꾸니까 효율성 테스트에서 통과했다.