HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 백준Python
  • Database
  • 프로그래머스Python
  • 코딩
  • 백엔드
  • 알고스팟
  • 프로그래밍
  • 백준Go
  • 데이터베이스
  • 알고스팟Python
  • back-end
  • 백준C++
  • front-end
  • Baekjoon Online Judge
  • programmers
  • 프로그래머스C++
  • 백준
  • 개발자
  • Algospot
  • 프로그래머스

최근 댓글

인기 글

hELLO
HelloMinchan

처음처럼

[programmers] 프로그래머스 예산 Level 3(Python)
Deprecated

[programmers] 프로그래머스 예산 Level 3(Python)

2020. 6. 7. 23:10

(주)그렙

[programmers] 프로그래머스 예산 Level 3

(Python)

(글쓴날 : 2020.06.07)

 


* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

프로그래머스 예산 Level 3


1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43237

 

코딩테스트 연습 - 예산

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그��

programmers.co.kr


2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

국가 예산의 총액과 지방의 예산 요청 리스트가 주어질 때, 전체 국가예산 이하에서 가능한 최대의 지방 예산 상한액을 구하는 문제입니다.

 

저의 경우, 이분 탐색을 적용하였고, Python을 사용했습니다.

지방의 예산 요청 리스트에서 가장 큰 금액을 right로 잡고 이분 탐색하였고, 문제에서 정의한 규칙에 상응하는 값 중 최대 상한액을 구하여 문제를 해결했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solution(budgets, M):
    answer = 0
    
    left = 0
    right = max(budgets)
    
    while(left <= right):
        mid = (left + right) // 2
        
        isPossible = True
        dividend = 0
        for b in budgets:
            if b <= mid:
                dividend += b
            else:
                dividend += mid
                
        if dividend > M:
            isPossible = False
        
        if isPossible:
            answer = mid
            left = mid + 1
            continue
            
        right = mid -1
             
    return answer

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[Baekjoon Online Judge] 백준 1916번 최소비용 구하기(Python)  (0) 2020.06.09
[Baekjoon Online Judge] 백준 1753번 최단경로(Python)  (0) 2020.06.09
[programmers] 프로그래머스 정수 삼각형(Python)  (0) 2020.06.07
[programmers] 프로그래머스 카카오프렌즈 컬러링북(C++)  (0) 2020.06.07
[programmers] 프로그래머스 스킬트리(Python)  (0) 2020.06.07
    'Deprecated' 카테고리의 다른 글
    • [Baekjoon Online Judge] 백준 1916번 최소비용 구하기(Python)
    • [Baekjoon Online Judge] 백준 1753번 최단경로(Python)
    • [programmers] 프로그래머스 정수 삼각형(Python)
    • [programmers] 프로그래머스 카카오프렌즈 컬러링북(C++)
    HelloMinchan
    HelloMinchan
    Though you should not fear failure, You should do your very best to avoid it.

    티스토리툴바