Programmers / 선입선출스케줄링 / Python 파이썬

2023. 3. 8. 15:57·coding test - python/Programmers
728x90
반응형

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 선입선출 스케줄링 (3단계) - 이분탐색

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12920

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

  • CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
  • 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
  • 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항
  • 코어의 수는 10,000 이하 2이상 입니다.
  • 코어당 작업을 처리하는 시간은 10,000이하 입니다.
  • 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

입출력 예ncoresresult
6 [1,2,3] 2
입출력 예 설명

입출력 예 #1
처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.


나의 풀이

def solution(n, cores):
    answer = 0
    if n <= len(cores): # n이 코어의 길이보다 작으면 n을 리턴
        return n
    n -= len(cores)
    start = 1
    end = max(cores) * n # n번째 작업량이끝나는 시간보다 큰 수 중 가장 작은 시간 구하기을 구하기
    
    while start < end:
        mid = (start + end) // 2
        jobs = 0
        for c in cores:
            jobs += mid//c # mid 시간 내에 한 코어당 끝낼 수 있는 작업의 총 갯수
            
        if jobs >= n:
            end = mid
        else:
            start = mid + 1
        
    for c in cores:
        n -= (end-1) // c 
        
    for i in range(len(cores)):
        if end % cores[i] == 0:
            n -= 1
            if n == 0:
                return i + 1

참고 사이트

https://dev-note-97.tistory.com/173

 


※ 알아야 할 것

- left = 1, right = max(cores) * n 에서 시작해서, mid = left + right // 2 로 계산해나가며, 만약 mid값의 총 작업수(capacity)가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이 목표

-  'n보다 큰 값 중 가장 작은 값'을 구하는 것이기 때문에, 이분탐색에서도 lower bound 알고리즘

- 작업량의 시간에 대해 이분탐색을 실시함

 

728x90
반응형

'coding test - python > Programmers' 카테고리의 다른 글

Programmers / 덧칠하기 / Python 파이썬  (0) 2023.03.14
Programmers / 귤 고르기 / Python 파이썬  (0) 2023.03.13
Programmers / 자물쇠와 열쇠 / Python 파이썬  (0) 2023.03.06
Programmers / 양과 늑대 -DFS / Python 파이썬  (0) 2023.02.27
Programmers / [1차] 셔틀버스 / Python 파이썬  (0) 2023.02.07
'coding test - python/Programmers' 카테고리의 다른 글
  • Programmers / 덧칠하기 / Python 파이썬
  • Programmers / 귤 고르기 / Python 파이썬
  • Programmers / 자물쇠와 열쇠 / Python 파이썬
  • Programmers / 양과 늑대 -DFS / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Python
    백준
    소수
    programmers
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
Programmers / 선입선출스케줄링 / Python 파이썬
상단으로

티스토리툴바