알고리즘 :: 마트 계산대, 이진 탐색

알고리즘 공부하며 배운내용

 

 

마트 계산대

마트에는 여러 대의 계산대가 있다.

손님들이 계산을 마치는 데 얼마나 걸리는지 궁금하다.

어떤 계산대는 빨리 끝나고, 어떤 계산대는 오래 걸린다.

그래서

비어있는 계산대로 가는 것보다, 빨리 끝나는 계산대에 기다리는게 더 빠른 경우도 있다.

 

예를 들어 6명의 손님이 5분, 7분 걸리는 계산대에 있다고 해보자.

5분 계산대가 3명 => 15분

7분 계산대가 2명 => 14분

여기서 남은 1명이 7분 계산대로 가면 21분

1분 기다려서 5분 계산대로 가면 20분에 끝난다.

즉 20분이면 계산이 다 끝난다

 

입력

두 줄을 받는다.

첫번째 줄: 손님 수 N

두번째 줄: 각 계산대에서 걸리는 시간이 공백으로 구분

예)

6

5 7

 

출력

모든 손님이 계산이 끝나는 최소 시간

 

 

핵심 포인트

계산 끝난 인원수 = 시간 / 계산대 걸리는 시간

6명의 손님이 있다면, 최초로 6명이 넘을 때 시간이 최소 걸린 시간

 

이진 탐색을 이용하면 더 효율적이라고 한다.

이진 탐색(Binary Search) 이란?=> 블로그 링크

코드 1 - 이진 탐색 X

시간이 흘러가게 하는게 포인트

1, 2, 3 . . . . . . . . 20, 21

1분 부터 모든 손님이 계산이 됐는지 확인하는 코드

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 sliding_window.txt로 저장했다.
let fs = require('fs')
let input = fs.readFileSync('mart_counter.txt').toString().split('\n')

// input 값 정리, 필요변수 선언
let customer = +input[0]
let counters = input[1].split(' ').map(Number)
let minute = 0
let done = 0

// 모든 손님 끝날 때까지 반복
while(done < customer) {
    done = 0
    
    // 시간 증가
    minute++
    
    // 흘러간 시간 / 계산대 시간
    for(let i = 0; i < counters.length; i++) {
        done += Math.floor(minute/counters[i])
    }
}

console.log(minute)

 

 

코드 2 - 이진 탐색 이용 (고민 중 . . . . . . .)