디너코딩

이 문제의 핵심은 현재 상황에서 가장 무거운 사람과 가장 가벼운 사람의 무게를 합친 무게가 주어진 무게 제한보다 작거나 같도록 짝꿍을 짓는 것입니다. 몸무게를 정렬해준 후 왼쪽 끝에서부터와 오른쪽 끝에서부터의 무게를 비교하여 최대한 많이 짝꿍을 지어줍니다. 

솔루션

def solution(people, limit):
    people=sorted(people)
    count,left,right=0,0,len(people)-1
    
    while left <= right:
        queue=[]
        if people[right]+people[left] <= limit:
            left+=1
        right-=1
        count+=1
    return count

이번 문제에서는 스택을 사용하여 문제를 풀어보았습니다. number의 자리수가 1,000,000자리이기 때문에 시간초과를 유의해야 합니다. 앞에서부터 차례대로 숫자를 stack에 저장하다가, 뒤에 나온 숫자가 저장된 숫자보다 클 시 pop해주고 뒤에 나온 숫자를 저장합니다. k개의 수를 제거할 수 있으므로 pop을 해줄 때마다 count를 해줍니다. 그 후, 만일 k가 양수라면 뒤에부터 k개만큼 제거하여 반환합니다.

솔루션

def solution(number, k):
    answer = ''
    idx=0
    a=['-1']
    num = len(number)
    length=num-k
    for i in range(len(number)):
        while a and a[-1] < number[i] and k>0:
            a.pop()
            k-=1
        a.append(number[i])
        
    return ''.join(a[:-k])

이분탐색은 원하는 값이 중간값보다 크다면 오른쪽을 탐색하고 중간값보다 작다면 왼쪽을 탐색하며 원하는 값을 탐색하는 기법입니다.

예를 들어, 1~10까지 상대가 생각한 수를 이분탐색 기법을 사용하여 찾아보겠습니다. 상대가 생각하는 수를 7이라고 생각해봅니다.

중간값 < 원하는 값 up

중간값 > 원하는 값 down

1. 1~10의 중간 값 = 5 -> up

2. 6~10의 중간 값 = 8 -> down

3. 6~8 의 중간 값 = 7 -> 답

입국심사 문제는 입국 심사하는데 걸리는 시간을 최소화하도록 입국 심사 하는 사람들을 심사대에 잘 배분하는 것입니다. 심사하는데 걸리는 시간을 각 심사대가 처리하는 시간으로 나눈 몫을 더하면 입국 심사 하는 사람들의 수가 나옵니다. 이 점을 활용하여 이분 탐색을 실시합니다. 

솔루션

def solution(n, times):
    left = 1
    right = n * min(times)
    mid=0
    while left < right:
        mid = (left+right) // 2
        m = 0
        for time in times:
            m += mid//time

        if m >= n:
            right = mid
        else:
            left = mid+1

    return left

left를 반환하는 이유는 입국 심사하는데 걸리는 최소한의 시간을 반환해야 하기 때문입니다.