728x90
반응형

문제:

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다
조건 2. n의 다음 큰 숫자는 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

우선 자연수 n의 이진수 값을 구하기 위해서 내장함수인 bin을 사용하였다. bin은 십진수의 값을 이진수로 변환해주는 함수다. 단 이진수 앞 부분에 '0x' 가 붙으며 문자열로 반환을 한다. 하지만 문제에선 1의 갯만 필요하므로 상관 없이 1의 갯수를 세주도록 한다.
이 후 다음 큰 숫자를 찾기 위해서 n부터 1씩 증가하며 n의 1의 갯수와 같을 때까지 계속 반복하면 된다.

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    answer=n
    n_count=bin(n).count('1')
    conti=True
    while conti:
        answer+=1
        temp=answer
        n_next_count=bin(temp).count('1')
        if n_count == n_next_count:
            break     
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.땅따먹기  (0) 2019.03.08
[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
728x90
반응형

문제:

올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.
예를 들어

"()()" 또는 "(())()"는 올바른 괄호입니다.
")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return하는 solution 함수를 완성해주세요.

풀이 방법:

'(' 는 +1의 값을 가지고 ')'이 -1의 값을 가진다고 하자.
모두 정상적으로 짝을 이뤘다. 즉 "(" 와 ")"의 갯수가 동일하다면 문자열 s를 반복문으로 한 번씩 탐색해보았을 때 count의 값이0이 되어야 할 것이다.
만약 count의 값이 양수가 나온다면 "("가 더 있는 것이고 음수면 그 반대일 것이다.
하지만 괄호의 갯수는 맞게 이루어져있지만 반대로 있을 수도 있다. (ex ")(" )
이와 같은 경우에는 문자열의 합은 0이 나오지만 올바르지 않은 괄호이다. 따라서 조건을 하나 더 추가를 해줘야 한다. 
문제가 발생 할 때에는 ")"에서 나오게 된다. "("로 열지도 않았는데 ")"로 닫아버릴 때 오류가 발생한다. 즉 count값이 순간적으로 마이너스가 될 경우가 오류가 발생하게 된다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(s):
    count=0
    for i in s:
        if i is '(':
            count+=1
        elif i is ')':
            count-=1
            if count < 0 :
                return False
    if count == 0:
        return True
    else:
        return False
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers] Lv 3. 등굣길  (2) 2019.03.07
[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
728x90
반응형

2019/02/13 - [Algorithm/Python] - [Programmers]Lv 1. 체육복


이전에 풀었던 문제인데 2.28일 이후로 테스트케이스가 추가되면서 하나의 케이스가 통과하지 못한다.

이전에는 조금 명시적으로 여분을 가지고 있는 학생이 구분이 되지 않았는데 더 명시적으로 여분을 가지고 있는 사람에게만 빌리게 하였더니 통과를 하였다.


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(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
        if i+1 in lost:
            cloth[i]-=1
    if cloth[0]==0:
        if cloth[1]==2:
            cloth[0]+=1
            cloth[1]-=1
    for i in range(1,n-1):
        if cloth[i]==0:
            if cloth[i+1]==2:
                cloth[i]+=1
                cloth[i+1]-=1
            elif cloth[i-1]==2:
                cloth[i]+=1
                cloth[i-1]-=1
    if cloth[-1]==0:
        if cloth[-2]==2:
            cloth[-1]+=1
            cloth[-2]-=1
    count=0
    for i in cloth:
        if i != 0:
            count+=1
    return count
cs

728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.다음 큰 숫자  (0) 2019.03.06
[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
728x90
반응형

문제:

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어 

수신 탑(높이) 

I 숫자 

큐에 주어진 숫자를 삽입합니다. 

D 1 

큐에서 최댓값을 삭제합니다. 

D -1 

큐에서 최솟값을 삭제합니다. 


이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값,최솟값]을 return 하도록 solution 함수를 구현해주세요.

풀이 방법:

힙을 사용해서 풀어야 하는 문제지만 굳이 힙을 사용해서 풀지 않아도 상관 없다. operations를 반복문의 매개변수로 받아 각 원소들을 공백으로 구분해보아서 명령어대로 배열에서 처리를 하면 문제없이 풀 수 있다. 삽입을 할 때 정수형으로 변경을 해서 넣는데 그 이유는 음수값들도 들어가기 때문에 정렬을 하기 위해서는 정수형으로 바꾸는 것이 필수적이기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(operations):
    answer=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            answer.append(int(b))
        else:
            if len(answer)>0:
                if b=="1":
                    answer.pop()
                else:
                    answer.pop(0)
            else:
                pass
        answer.sort()
    if len(answer)==0:
        return [0,0]
    else:
        return [max(answer),min(answer)]
cs

만약 힙을 사용해서 풀고 싶다면 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
def solution(operations):
    h=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            heapq.heappush(h,int(b))
        else:
            if len(h)>0:
                if b=="1":
                    h.pop(h.index(heapq.nlargest(1,h)[0]))
                else:
                    heapq.heappop(h)
            else:
                pass
    if len(h)==0:
        return [0,0]
    else:
        return [heapq.nlargest(1,h)[0],heapq.nsmallest(1,h)[0]]
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.올바른 괄호  (0) 2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
728x90
반응형

문제:

1과 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.( 단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이 방법:

이 문제는 DP(dynamic programming), 동적계획법을 사용해서 풀어야 하는 문제이다. 왼쪽 위(1,1)부터 시작해서 오른쪽 아래로 진행을 하면서 정사각형을 나간다. 

정사각형으로 취급되는 경우는 다음과 같다.


1(1번)

1(2번) 

 1(3번) 

1(4번) 


4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어 준다. 즉 다음과 같이 된다.


1(1번)

1(2번) 

 1(3번) 

2(4번) 


최솟값을 찾는 이유는 하나의 0이 있다면 정사각형의 형태가 아니므로 1 이상의 값들만 이어나가기 위함이다. 또한 1을 더해주는 이유는 정사각형이라면 길이의 값을 누적하기 위해서이고 아니라면 남은 1의 값들이 다른 곳에서 정사각형을 이룰 수 있기 때문에 이어나가주는 것이다.

이 문제의 예시를 통해서 구하는 방법을 알아보자. 다음과 같이 처음 상태가 있다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


처음 왼쪽 위 (1,1)을 비교해 보았을 때 (0,0)이 0이기에 (1,1)의 값을 1로 바꾼다.


0 

1 

1 

1

1 

1 

1 

1

1 

1 

1

1

0

0

1

0


(1,2)의 값을 비교해 보았을 때  주위 최솟값이 1이므로 (1,2)의 값을 2로 바꾼다. 이 경우가 길이가 2인 정사각형을 찾은 경우이다. 하지만 가장 큰 정사각형을 찾는 것이 문제이므로 계속 탐색해보도록 한다.

0 

1 

1 

1

1 

1 

2

1

1 

1 

1

1

0

0

1

0


(1,3)의 값을 비교해보았을 때, 주위 최솟값이 1이므로 (1,3)의 값을 2로 바꾼다. 이 경우도 역시 길이가 2인 정사각형을 찾은 경우다. 이전 (1,2)에서도 정사각형을 찾았지만 이 둘로는 정사각형이 아닌 직사각형이 만들어지므로 서로 영향을 주진 못한다.

0 

1 

1 

1

1 

1 

2 

2

1 

1 

1

1

0

0

1

0


계속해서 이 방법대로 진행을 하면 (2,2)까지 다음과 같이 표를 바꿀 수 있다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

1

0

0

1

0


(2,3)에서는 주위의 최솟값이 2이므로 (2,3)의 값을 3으로 바꾼다 즉 길이가 3인 정사각형을 찾은 경우다. 이 처럼 주위의 값들이 모두 2,2,2 혹은 3,3,3 과 같이 이루어져 있을 경우에 가장 큰 정사각형의 길이가 바뀌게 되는 것이다.

0 

1 

1 

1

1 

1 

2 

2

1 

2 

2

3

0

0

1

0


마지막 줄은 계속 진행해보아도 변경되는 점이 없으므로 이 예시의 가장 큰 정사각형은 길이가 3인 정사각형이다.

다른 채점케이스에서 전부다 0인 경우에는 위와 같은 방법으로 길이가 1인 정사각형이 있다고 나오므로 따로 구분해서 구하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(board):
    max_point=0
    for i in range(len(board)):
        max_point+=sum(board[i][:])
    if max_point==0:
        return 0
    max_point=0
    for i in range(1,len(board)):
        for j in range(1,len(board[0])):
            if board[i][j]==0:
                continue
            else:
                min_point=min(board[i][j-1],board[i-1][j],board[i-1][j-1])
                min_point+=1
                board[i][j]=min_point
                if max_point < board[i][j]:
                    max_point=board[i][j]
    if max_point==0:
        return 1
    else:
        return max_point**2
cs




728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1. 체육복(테스트케이스 수정)  (0) 2019.03.03
[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
728x90
반응형

2019/02/25 - [Algorithm/Python] - [Programmers]:Lv 3. 예산

문제:

n 명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그 곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이분탐색 문제이므로 이 문제도 예산 문제와 같이 심사를 다 받는 시간을 찍어보면 된다. 왼쪽 값을 0 우측 값을 times의 가장 큰 값에 n을 곱한 값으로 설정하고 이분 탐색을 진행해 나가면 된다. 중간에 n명을 통과를 할 수 있는 시간이 있더라도 최소값을 찾기 위해 끝까지 진행해본다.
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(n, times):
    left=0
    right=max(times)*n
    temp=right
    answer=right
    while(right>=left):
        mid=(right+left)//2
        people=0
        for i in times:
            people+=mid//i
        if people==n:
            if answer>=mid:
                answer=mid
            right=mid-1
        elif people>n:
            right=mid-1
        else:
            left=mid+1
    if answer==temp:
        return right+1
    else:
        return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 이중우선순위큐  (1) 2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
728x90
반응형

문제:

 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1,1,1,1,1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1=3
+1-1+1+1+1=3
+1+1-1+1+1=3
+1+1+1-1+1=3
+1+1+1+1-1=3

 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟
넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS)는 트리 구조를 만드는 것이 핵심이다. 이 문제에서 타겟 넘버를 만드는 방법은 더하거나 빼거나 둘 중 하나다. 따라서 하나의 숫자에 대해 다음 값을 더하는 경우, 빼는 경우로 트리 구조를 만들어 나갈 수 있는 것이다. 첫 수부터 빼는 경우가 있을 수 있으므로 미리 0을 담아 놓고 시작 하도록 한다. 이후 트리를 다 완성 시킨 후 타겟 넘버인 target의 갯수를 카운트 하면 된다.


1
2
3
4
5
6
7
8
9
10
def solution(numbers, target):
    answer_list=[0]
    for i in numbers:
        temporary_list=[]
        for j in answer_list:
            temporary_list.append(j+i)
            temporary_list.append(j-i)
        answer_list=temporary_list
    answer = answer_list.count(target)
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.가장 큰 정사각형 찾기  (0) 2019.03.02
[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
728x90
반응형

문제:


위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.


삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.


풀이 방법:

동적계획법 문제임을 이용해서 꼭대기에서 부터 업데이트 해가면서 풀어야 하는 문제이다. 한 칸을 업데이트를 할 경우에는 크게 두 가지가 경우가 있다.

1. 양쪽 끝일 때


양쪽 끝의 숫자들은 다음과 같이 그 전 칸의 처음 혹은 끝의 영향만을 받는다. 따라서 별도의 비교 없이 업데이트 해가면 된다.


2. 그 외의 경우



가운데에 있는 숫자들은 두 개의 숫자를 비교를 해야 한다. 가장 큰 경우를 구해야 하므로 둘 중 큰 경우를 선택해서 더해주면 된다.


위의 규칙을 따라서 다음과 같은 순서로 진행이 된다.


       7

      3 8

     8 1 0

    2 7 4 4

   4 5 2 6 5


예시와 같이 이러한 삼각형이 있다고 하면 처음에는 양쪽 끝에만 영향을 주는 경우 이므로 7을 각각 더해준다.


        7

     10 15

    8  1  0

   2  7  4  4

  4 5  2  6  5


8과 0의 경우에는 1번 경우이므로 10과 15를 각각 더해주면 되고 1은 10과 15중 15가 더 크므로 15를 더해 주도록 한다.


        7

     10 15

   18 16 15

   2   7  4   4

 4   5   2  6  5


2와 맨 끝의 4의 경우엔 1번이므로 18과 15를 각각 더해주고 7은 18과 16 중 18이 더 크므로 18을 더하고 4는 16과 15 중 16이 더 크므로 16을 더한다.


        7

     10 15

   18 16 15

  20 25 20 19

 4   5  2   6   5


위와 같은 방법으로 계속 더해가면 된다.


        7

     10 15

   18 16 15

  20 25 20 19

24 30 27 26 24


이후 맨 마지막 인덱스 배열의 최댓값을 구하면 30을 얻을 수 있다.


1
2
3
4
5
6
7
8
9
10
def solution(triangle):
    for i in range(1,len(triangle)):
        for j in range(i+1):
            if j==0:
                triangle[i][j]+=triangle[i-1][j]
            elif j==i:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
    return max(triangle[-1])
cs



728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 입국 심사  (2) 2019.03.01
[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
728x90
반응형

문제:

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤씁니다.


Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.


Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로,세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.


풀이 방법:

이 카펫은 내부에 있는 빨간색의 모양에 따라서 갈색으로 칠한 수가 정해지게 된다. 이 문제가 완전탐색이므로 빨간색의 갯수로 나올수 있는 경우의 수를 모두 구해서 알맞은 경우를 찾도록 한다.
안의 빨간색의 모양은 사각형의 모양이므로 red의 약수마다 갈색의 갯수를 구한다. 이때 brown과 같아진다면 그 경우가 답이 되는 것이다.

1
2
3
4
5
6
7
8
9
10
def solution(brown, red):
    answer=[]
    for i in range(1,int(red/2)+2):
        if red%i==0:
            a,b=max(red//i,i),min(red//i,i)
            if 2*a+(b+2)*2==brown:
                answer.append(a+2)
                answer.append(b+2)
                break
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 타겟 넘버  (0) 2019.02.28
[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]:Lv 3. 예산  (0) 2019.02.25
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
728x90
반응형

문제:

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다.
   상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120,110,140,150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120,110,127,127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

이 문제는 처음 봤을 때, 예시를 보면 120~150 사이의 수를 모두 넣어보아서 최대가 되는 상한액을 찾으면 되는 것이 아닌가 라고 생각 할 수 있지만 그렇게 푼다면 아마 시간초과가 발생할 것이다.(총 예산이 1,000,000,000 이하인 수이다..)
따라서 이 문제의 태그가 이분탐색인 만큼 이분탐색을 사용해야 시간초과가 발생하지 않고 풀 수 있다. 이분탐색의 문제의 핵심은 '찍기'라고 생각하면 된다. 이 문제의 예시로 예를 들어보면 0~150의 수를 이분탐색의 방법으로 찍어가면서 최대 상한액을 찾아나가는 것이다.

처음에는 75를 상한액으로 고를 수 있고 75*4<=485이므로 왼쪽 값을 75+1로 선택하여 이분탐색을 진행한다.
그 다음엔 113을 상한액으로 고를 수 있고 이 역시 113*3+110<=485이므로 왼쪽값을 113+1로 선택하여 이분탐색을 진행한다.
그 다음엔 132를 상한액으로 고를 수 있고 120+110+132*2>=485이므로 오른쪽 값을 132-1로 선택하여 이분탐색을 진행한다.
이와 같이 계속 반복하다보면 127이 상한액일 때 최대가 됨을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(budgets, M):
    left=0
    right=max(budgets)
    temp=0
    answer=0
    while(right>=left):
        mid=(left+right)//2
        result=0
        for i in budgets:
            if mid>i:
                result+=i
            else:
                result+=mid
        if result>M:
            right=mid-1
        else:
            if result>=temp:
                answer=mid
            left=mid+1
    return answer
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 정수 삼각형  (0) 2019.02.27
[Programmers]Lv 2. 카펫  (0) 2019.02.26
[Programmers]Lv 2. 구명 보트  (0) 2019.02.24
[Programmers]Lv 3.타일 장식물  (0) 2019.02.23
[Programmers]Lv 2. 숫자 야구  (0) 2019.02.22

+ Recent posts

티스토리툴바