[백준]대표선수, [백준]입국심사

https://www.acmicpc.net/problem/2461

2461번: 대표 선수

1) 투포인터를 사용해 정렬한 리스트의 첫번째 요소들끼리 비교

2) 비교한 요소들의 최소, 최대를 구하고 diff 계산.

3) 최소값을 가진 리스트 인덱스 +1, 새 리스트를 구성해 최소 최대를 구해줌

4) 최소값을 가진 리스트 인덱스가 리스트 끝이면 종료

 

----> 시간초과.   So. 힙 사용

 

import sys
import heapq

def solution(arr, n,m):
    hq = []
    max_value = 0
    arr_class = [0] * n
    arr_pointer = [0] * n
    min_diff = int(10e9)
    #첫번째 index 리스트들의 최대,최소 초기화
    for i in range(n):
        max_value = max(arr[i][0], max_value)
        heapq.heappush(hq, (arr[i][0],i))
    
    while True:
        min_student = heapq.heappop(hq)
        min_value = min_student[0]
        min_index = min_student[1]        
        min_diff = min(min_diff, max_value - min_value)

        arr_pointer[min_index] +=1 #최소값을 가지고 있는 학급 학생 포인터 +1   

        if arr_pointer[min_index] == m:
            break
        
        heapq.heappush(hq, (arr[min_index][arr_pointer[min_index]], min_index))
        max_value = max(max_value, arr[min_index][arr_pointer[min_index]])
    print(min_diff)
    
n,m = map(int,sys.stdin.readline().split())
arr = list()
for _ in range(n):
    arr.append(sorted(map(int, sys.stdin.readline().split())))

solution(arr,n,m)

 

 

https://www.acmicpc.net/problem/3079

3079번: 입국심사

 

이분탐색

 

1) m의 길이가 10억으로 구현X, 이분탐색으로 시간을 mid로 잡아 구현

2) 심사대 최소 시간을 left, 심사대 최대시간 * m 으로 right, mid --> (left + right) //2

3) while문을 사용해 left <= right 조건 사용. 각 심사대가 mid 시간에 처리할 수 있는 인원의 수를 total 변수에 담아 계산.

만약 total >=m 이면 right = mid - 1, 정답을 비교해 교체. 만약 total <m 이면, left = mid + 1

 

import sys

def solution(n,m,time):
    left = min(time)
    right = max(time)*m
    ans = right
    
    while left<=right:
        total = 0
        mid = (left+right) // 2
        for t in time:
            total += mid // t
            if total >= m:
                right = mid - 1
                ans = min(ans, mid)
                break
        else:
            left = mid +1
    return ans

n,m = map(int, sys.stdin.readline().split())
time = [*map(int, sys.stdin.readlines())]

print(solution(n,m,time))