프로그래머스 입국심사 (이분탐색)

• 예전에 C++로 풀었는데, 시간 초과가 났었다.
• 다시봐도 C++은 어우... 이젠 못 쓰겠다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    sort(times.begin(), times.end());
    
    vector<int> officer = times;
    
    int passed = 0;
    int i = 0;
    
    while(passed < n)
    {
        officer[i]--;

        if(officer[i] <= 0){
            passed++;
            officer[i] = times[i];
        }
        
        i++;
        if(i >= officer.size()){
            answer++;
            i = 0;
        }
    }
    
    return answer+1;
}

• 일단 이걸 파이썬으로 먼저 옮긴다.
• 물론 결과는 동일. 시간초과.

def solution(n, times):
    answer = 0
    times.sort()
    officer = times.copy()
    passed = 0
    i = 0
    
    while passed < n:
        officer[i] -= 1

        if officer[i] <= 0:
            passed += 1
            officer[i] = times[i]
        
        i += 1
        if i >= len(officer):
            i = 0
            answer += 1
            
    return answer + 1

• 이런 방식으로는 안되는 ㅋㅋ

def solution(n, times):
    answer = 0
    times.sort()
    officer = times.copy()
    len_officer = len(officer)
    passed = 0
    
    while passed < n:
        min_time = min(officer)
        for i in range(len_officer):
            officer[i] -= min_time
            if officer[i] == 0:
                passed += 1
                officer[i] = times[i]
        answer += min_time
            
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.1MB)
테스트 2 〉	통과 (6.88ms, 10.3MB)
테스트 3 〉	통과 (1065.73ms, 10.3MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)

• 킁...

def solution(n, times):
    answer = 0
    times.sort() # 처리 시간
    
    officers = [] # 처리한 인원 수
    officers.append(int(n/len(times)))
    
    passed_time = times[0] * officers[0]
    
    for i in range(1, len(times)):
        officers.append(int(passed_time / times[i]))
    
    for i in range(0, len(times)):
        print("속도:", times[i],"처리 인원:", officers[i],"소요 시간:", times[i] * officers[i])
    print("남은 인원:", n-sum(officers))
    
    return answer
    
테스트 1
입력값 〉	6, [7, 10]
기댓값 〉	28
실행 결과 〉	실행한 결괏값 0이 기댓값 28과 다릅니다.
출력 〉	
속도: 7 처리 인원: 3 소요 시간: 21
속도: 10 처리 인원: 2 소요 시간: 20
남은 인원: 1

• 힝... 왜 안되는거야;

import numpy as np

def solution(n, times):
    answer = 0
    times.sort() # 처리 시간
    
    officers = [] # 처리한 인원 수
    officers.append(int(n/len(times)))
    officers_time = []
    
    passed_time = times[0] * officers[0]
    
    for i in range(1, len(times)):
        officers.append(int(passed_time / times[i]))
    
    fast_officer = min(officers)
    for i in range(len(times)):
        #print("속도:", times[i],"처리 인원:", officers[i],"소요 시간:", times[i] * officers[i])
        officers_time.append(times[i] * officers[i])
    #print("남은 인원:", n-sum(officers))
    
    answer = min(officers_time)
    #print(answer)
    estimated_officers_time = officers_time.copy()
    n = n - sum(officers)
    
    for i in range(len(officers_time)):
        estimated_officers_time[i] += times[i]

    sorted_officers_time  = np.sort(estimated_officers_time)
    sorted_officers_index = np.argsort(estimated_officers_time)

    for i in range(n):
        #officers[sorted_officers_index[i]] += 1
        officers_time[sorted_officers_index[i]] += times[sorted_officers_index[i]]
    
    return max(officers_time)

테스트 1
입력값 〉	6, [7, 10]
기댓값 〉	28
실행 결과 〉	테스트를 통과하였습니다.

테스트 2
입력값 〉	7, [7, 10]
기댓값 〉	30
실행 결과 〉	테스트를 통과하였습니다.

정확성  테스트
테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	실패 (런타임 에러)
테스트 4 〉	실패 (172.63ms, 42.7MB)
테스트 5 〉	실패 (런타임 에러)
테스트 6 〉	실패 (런타임 에러)
테스트 7 〉	실패 (런타임 에러)
테스트 8 〉	실패 (런타임 에러)
테스트 9 〉	실패 (런타임 에러)

• 라운드 로빈 방식 같은건 그냥 안된다.
  • 시간 초과...

import numpy as np

def solution(n, times):
    num_people = len(times)
    current_time = [0] * num_people
    while n > 0:
        for i in range(num_people):
            if n <= 0:
                break
            current_time[i] += times[i]
            n -= 1
    return max(current_time)
    
정확성  테스트
테스트 1 〉	실패 (0.01ms, 27.9MB)
테스트 2 〉	실패 (0.13ms, 28.2MB)
테스트 3 〉	실패 (0.80ms, 28.2MB)
테스트 4 〉	실패 (15.61ms, 35.6MB)
테스트 5 〉	실패 (54.60ms, 39.8MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)

• 한 번 더 트라이!

import numpy as np

def solution(n, times):
    num_people = len(times)
    average_time = 0
    officers = [[0,0] for i in range(num_people)]
    for i in range(num_people):
        average_time += 1/times[i]
        
    target = int(n / average_time + 0.9) + 1
    
    for i in range(num_people):
        officers[i][1] = target // times[i]
        officers[i][0] = times[i] * (target // times[i])
        n -= officers[i][1]
    
    remind = [[0,0] for i in range(num_people)]
    if n > 0:
        for i in range(num_people):
            next_time = officers[i][0] + times[i]
            remind[i][0] = next_time
            remind[i][1] = i #index

        remind.sort()
    
    if remind[n-1][0] != 0:
        return remind[n-1][0]
    else:
        return max(officers[i][0] for i in range(num_people))

• 이게 안되네?

정확성  테스트
테스트 1 〉	실패 (0.02ms, 28.2MB)
테스트 2 〉	실패 (0.24ms, 28.2MB)
테스트 3 〉	통과 (1.26ms, 28.5MB)
테스트 4 〉	실패 (239.64ms, 55.6MB)
테스트 5 〉	통과 (217.75ms, 60.4MB)
테스트 6 〉	통과 (273.62ms, 61.8MB)
테스트 7 〉	실패 (335.51ms, 63.5MB)
테스트 8 〉	통과 (270.54ms, 63.5MB)
테스트 9 〉	실패 (런타임 에러)

• 결국 시키는 대로 이분탐색으로 ㅠ.ㅠ
  • n명이 입국심사를 받는 최소 시간 = 제일 빠른 심사대
  • n명이 입국심사를 받는 최대 시간 = 제일 느린 심사대 * n명

def solution(n, times):
    times.sort()
    min_time = times[0]
    max_time = times[-1]* n
        
    def binSearch(low, high):
        mid = (high-low)//2
        if mid == 0:
            return high
        mid += low
        
        passed = 0
        for t in times:
            passed += mid // t
            
        if passed >= n:
            return binSearch(low, mid)
        else:
            return binSearch(mid, high)
        
    return binSearch(min_time, max_time)

• 괜한 고집이었다.
  • 시키는대로 하는게 제일 쉽다.

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.10ms, 10.3MB)
테스트 3 〉	통과 (4.03ms, 10.1MB)
테스트 4 〉	통과 (381.12ms, 14MB)
테스트 5 〉	통과 (488.09ms, 14.2MB)
테스트 6 〉	통과 (338.49ms, 14.4MB)
테스트 7 〉	통과 (659.35ms, 14MB)
테스트 8 〉	통과 (652.15ms, 14MB)
테스트 9 〉	통과 (0.04ms, 10.2MB)

• 고수의 풀이
  • 신기한 방식...

def count(period, times):
    cnt = 0
    for time in times:
        cnt += period // time
    return cnt

def solution(n, times):
    digit = 50
    t = 0
    for i in range(digit, -1, -1):
        temp  = t + 2**i
        cnt = count(temp, times)
        if cnt >= n:
            if count(temp-1, times) < n:
                return temp
        else:
            t = temp
            
정확성  테스트
테스트 1 〉	통과 (0.19ms, 10.2MB)
테스트 2 〉	통과 (0.66ms, 10.2MB)
테스트 3 〉	통과 (7.16ms, 10.1MB)
테스트 4 〉	통과 (659.91ms, 14.2MB)
테스트 5 〉	통과 (853.45ms, 14.3MB)
테스트 6 〉	통과 (634.52ms, 14.2MB)
테스트 7 〉	통과 (1062.84ms, 14.2MB)
테스트 8 〉	통과 (995.41ms, 14.1MB)
테스트 9 〉	통과 (0.10ms, 10.2MB)

• 비슷비슷하다.

def solution(n, times):
    answer = 0
    begin = 0
    end = 1 * 10 ** 18
    times.sort()
    while (begin <= end):
        to_do_job = [n][0]
        mid = (begin + end) // 2
        for task_time in times:
            to_do_job -= mid // task_time
        if to_do_job <= 0:
            end = mid -1
        elif to_do_job > 0:
            begin = mid +1
    return begin
    
정확성  테스트
테스트 1 〉	통과 (0.06ms, 10.3MB)
테스트 2 〉	통과 (0.46ms, 10.1MB)
테스트 3 〉	통과 (9.54ms, 9.99MB)
테스트 4 〉	통과 (992.07ms, 14.2MB)
테스트 5 〉	통과 (764.32ms, 14.3MB)
테스트 6 〉	통과 (1183.25ms, 14.5MB)
테스트 7 〉	통과 (1187.45ms, 14MB)
테스트 8 〉	통과 (624.74ms, 14.2MB)
테스트 9 〉	통과 (0.03ms, 10.3MB)

• 나중에 시간 되면 평균 속도로 찾아보는거 다시 짜봐야지