AndroidTeacher

programmers.co.kr/learn/courses/30/lessons/72412

문제 설명

문제에 대한 설명이 굉장히 길어 링크로 대체합니다.

간단히 설명하자면, info에 있는 목록 중 query에 있는 목록을 만족하는 개수를 구하는 문제입니다.

풀이 과정

처음에는 딕셔너리와 이분탐색을 이용하지 않고, 주어진 리스트를 그대로 이용해

각 리스트 요소마다 하나씩 매번 검사하는 방법을 이용했습니다.

정확성은 통과를 했지만, 역시 효율성에서 실패했습니다.

방법 1

정확성 성공

효율성 실패

from itertools import combinations


def solution(info, query):
    answer = [0 for i in range(len(query))]
    infol = []
    queryl = []
    for i in range(len(info)):
        infol.append(info[i].split())
        # tmp = ['java', 'backend', 'junior', 'pizza', '150']
    for j in range(len(query)):
        queryl.append(query[j].split())
        while len(queryl[j]) > 5:
            queryl[j].remove("and")

    for i in range(len(infol)):
        for j in range(len(queryl)):
            flag = 0
            for k in range(4):
                if infol[i][k] != queryl[j][k]:
                    if queryl[j][k] != '-':
                        flag = 1
                        break
            if flag == 0:
                if int(infol[i][4]) >= int(queryl[j][4]):
                    answer[j] += 1

    return answer

효율성을 통과하기 위해 사용한 방법은,

딕셔너리(자바의 hash와 비슷한 파이썬의 자료구조), 이분탐색(BinarySearch)를 이용했습니다.

과정은 다음과 같습니다.

① info 안의 문자열을 공백을 기준으로 분리합니다. ( ex ['java', 'backend', 'junior', 'pizza', '150'] )

② 분리한 것 중, 앞의 4부분(java,backend..)을 키값으로, 마지막부분(150)을 value값으로 분리 합니다.

③ 키값들로 만들 수 있는 모든 조합을 생성합니다. (combinations 이용)

④ 이 조합으로 딕셔너리를 생성합니다. 해당 키값이 딕셔너리에 이미 존재하면 value값을 그 키의 value값에 추가합니다.    { 'javabackendjuniorpizza' : [150...] , 'java' : [100...] , ... } 식으로 생성이 되겠죠?

⑤ 딕셔너리의 각 원소마다 value값들을 기준으로 정렬합니다. [100,150,200...]식으로 되도록

⑥ query도 마찬가지로 분리합니다. ( query에는 and와 -도 있기 때문에 제거를 하여 info와 같은 형식으로 만듭니다. )

⑦ 이제 query를 한바퀴 돌면서, info딕셔너리를 탐방하게 되는데,

    query의 key값이 info딕셔너리의 키값으로 존재하면 그 info딕셔너리의 value값들을 가져옵니다.

⑧ 가져온 점수값에서 기준 점수값을 넘는 것들의 개수를 이분탐색을 통해 구하면 됩니다.

방법 2

정확성 성공

효율성 성공

from itertools import combinations
from bisect import bisect_left


def solution(info, query):
    answer = []
    info_dict = {}

    for i in range(len(info)):
        infol = info[i].split()  # info안의 문자열을 공백을 기준으로 분리
        mykey = infol[:-1]  # info의 점수제외부분을 key로 분류
        myval = infol[-1]  # info의 점수부분을 value로 분류

        for j in range(5):  # key들로 만들 수 있는 모든 조합 생성
            for c in combinations(mykey, j):
                tmp = ''.join(c)
                if tmp in info_dict:
                    info_dict[tmp].append(int(myval))  # 그 조합의 key값에 점수 추가
                else:
                    info_dict[tmp] = [int(myval)]

    for k in info_dict:
        info_dict[k].sort()  # dict안의 조합들을 점수순으로 정렬

    for qu in query:  # query도 마찬가지로 key와 value로 분리
        myqu = qu.split(' ')
        qu_key = myqu[:-1]
        qu_val = myqu[-1]

        while 'and' in qu_key:  # and 제거
            qu_key.remove('and')
        while '-' in qu_key:  # - 제거
            qu_key.remove('-')
        qu_key = ''.join(qu_key)  # dict의 key처럼 문자열로 변경

        if qu_key in info_dict:  # query의 key가 info_dict의 key로 존재하면
            scores = info_dict[qu_key]

            if scores:  # score리스트에 값이 존재하면
                enter = bisect_left(scores, int(qu_val))

                answer.append(len(scores) - enter)
        else:
            answer.append(0)

    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/12015

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다.

예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다.

풀이 과정

먼저, 풀이과정 두가지를 이용할 수 있는데,

하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고

다른 하나는 내장 모듈인 bisect를 이용한 방법이다.

먼저 풀이1번 부터 설명하자면,

array는 문제에서 설명한 수열A를 나타낸다. A에 수열의 모든 원소들을 저장한다.

stack은 정답을 나타낼 가장 긴 증가하는 부분수열을 나타낼 것이다.

for문 부분부터 살펴보면, 수열A를 처음부터 돌면서 수열들을 뽑아내게 되는데

현재 원소가 stack의 마지막 원소보다 크다면, 당연히 수열을 연장할 수 있으므로 stack의 마지막에 추가한다.

하지만 그렇지 않다면? 버려야 할까?

그렇지 않다.

만약, 현재 stack이 10, 20, 40, 60으로 구성되어 있고, 현재 50이 들어갈 자리가 60이 있는 자리인 상황이라면

60을 50으로 교체해야 더 긴 수열을 연장할 수 있다.

왜냐하면, 10, 20, 40, 60 일때 55가 들어온다면 연장할 수 없지만 10, 20, 40, 50 일 경우에는 연장할 수 있기 때문이다.

그래서, else문에 stack[binary_search(i, 0, len(stack) - 1)] = i 라는 조건을 준 것이다.

n = int(input())
array = list(map(int, input().split()))
stack = [0]


def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start


for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[binary_search(i, 0, len(stack) - 1)] = i

print(len(stack) - 1)

다른 풀이과정은 간단하다, 

bisect_left는 리스트에서 i라는 원소가 들어갈 가장 왼쪽 위치를 반환해주는 함수이다.

위 방법과 마찬가지로 stack의 가장 마지막 원소가 현재 진입하려는 원소보다 작으면 뒤로 이어서 붙여주면 되고,

아닌 경우에는 이진탐색을 통해 해당 인덱스의 원소를 교체해주면 된다.

from bisect import bisect_left

n = int(input())
array = list(map(int, input().split()))
stack = [0]

for i in array:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[bisect_left(stack, i)] = i

print(len(stack)-1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/1300

문제 설명

이 문제에서 A라는 배열의 각 칸에는 다음과 같이 자기 인덱스의 곱을 담고있다. ( 즉 N[2][3] = 2*3 )

이러한 배열을 B라는 1차원 배열에 오름차순으로 나타내었을 때, k번째 인덱스에는 어떤 수가 있는지를 출력하는 문제이다.

풀이 과정

처음에는 N*N크기의 1차원 배열을 만들어 for문을 이용해 1*1부터 N*N까지의 수를 모두 넣어주고 정렬을 한 후에

그 배열의 k번째 수를 출력하도록 설계하였다.

하지만 문제에서 N은 10^5보다 작거나 같은 자연수이기 때문에 N*N크기의 배열을 만들려면 10^10만큼의 굉장히 많은 메모리가 필요했고 결과도 마찬가지로 메모리 초과가 나왔다.

이러한 큰 메모리 문제가 발생하는 경우의 탐색은 이분탐색으로 접근하면 쉽게 해결할 수 있다.

따라서 많은 고민끝에 다음과 같이 접근하였다.

1) N*N의 모든 수를 구할 필요 없이, 내가 구하고자 하는 K번째 인덱스 까지만 알면 된다.

2) 2차원 배열의 각 칸들의 값은 i*j 형태를 띄므로, 일정한 규칙이 존재한다.

3) 이 규칙에 따르면, 임의의 수 a보다 작거나 같은 수의 개수를 구하는 식이 존재한다.

4) 각 행은 구구단처럼 1단 2단 3단... 식으로 나타나기 때문에 ( a / 행번호 ) 가 그 행에서 구하고자 하는 개수가 된다.

   단, (a / 행번호) 가 N보다 클 경우에는 N이다.

   예를들어, 임의의 수 a를 4라고 했을 때, 1행은 4 / 1 = 4 이지만 N이 3이므로 3개이며

   4 / 2 = 2 이므로 2행은 2개, 4 / 3 = 1 이므로 3행은 1개이다.

이러한 접근방식을 이용하여 이분탐색을 진행하여 내가 구하고자 하는 인덱스를 마주하게 되면 정답이 된다.

이분탐색에서 사용했던 방법 똑같이, 내가 구하고자 하는 target(인덱스)가 mid값(임의의 인덱스)보다 작으면 end값을 줄여 탐색 범위를 좁히면 되고,

target이 mid값보다 크면 start값을 높여 탐색 범위를 좁히면 된다.

n = int(input())
k = int(input())

def binary_search(target, start, end):
    while(start <= end):
        mid = (start + end) // 2

        cnt = 0
        for i in range(1, n+1):
            cnt += min(mid//i, n)

        if cnt >= target:
            end = mid-1
        else:
            start = mid+1
    return start


print(binary_search(k,1,n*n))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/10816

지난번에 풀었던 10815번 숫자카드 1 문제의 상위 호환 문제이다.

숫자카드1 문제의 경우 이진탐색을 하여 찾고자 하는 숫자가 있으면 단순히 1을 출력하는 문제였다면,

이 문제는 찾고자 하는 숫자의 개수까지 구해야 한다.

<방법1>

처음에는 숫자카드 1처럼 이진탐색을 한 후에 찾은 숫자는 리스트에서 제외를 해주고 다시 이진탐색을 추가하는 식으로 해서 개수를 구했는데, 이진탐색임에도 불구하고 시간초과 오류가 났다.

<방법2>

그래서 다음으로 찾은 방법은

이진 탐색을 진행하여 찾고자하는 숫자를 찾게되면 그 숫자만 count함수를 이용해서 개수를 구한 방법이다.

코드는 첨부하지만, 이 방법도 40%쯤 지나갔을 때 시간초과 오류가 발생했다.

from sys import stdin
n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

card.sort()

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return array[start:end+1].count(target)
    elif array[mid] < target:
        return binary_search(array, target, mid+1, end)
    else:
        return binary_search(array, target, start, mid-1)

for i in range(len(test)):
    a = binary_search(card, test[i], 0, len(card)-1)
    if a is not None:
        print(a, end=' ')
    else:
        print(0, end=' ')

<방법3>

그래서 다음으로 찾은 방법은,

파이썬 내장 모듈인 bisect를 이용해서 풀었고, 시간초과 오류 없이 통과하였다.

bisect는 파이썬에 내장되어있는 이진탐색 모듈인데

bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스,

bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 알려준다.

이를 이용하여 count_by_range라는 함수를 만들어 주었는데

이 함수의 인자인 left_value와 right_value 사이에 존재하는 숫자들의 갯수를 반환하는 함수이다.

따라서 left_value와 right_value에 같은 값을 주게 되면 그 숫자의 갯수를 세게 되는 것이다.

from bisect import bisect_left, bisect_right
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))
card.sort()

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


for i in range(len(test)):
    print(count_by_range(card, test[i], test[i]), end=' ')

<방법4>

파이썬 내장 모듈인 Counter 이용

Counter는 리스트를 값으로 주게 되면 해당 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환한다.

from collections import Counter
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

count = Counter(card)

for i in range(len(test)):
    if test[i] in count:
        print(count[test[i]], end=' ')
    else:
        print(0, end=' ')

<방법5>

해쉬맵 이용 ( 파이썬에서는 딕셔너리 )

방법4의 Counter와 비슷하지만 직접 해쉬맵을 만들어 구현하였다.

from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

hash = {}

for i in card:
    if i in hash:
        hash[i] += 1
    else:
        hash[i] = 1

for i in test:
    if i in hash:
        print(hash[i], end=' ')
    else:
        print(0, end=' ')

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/1654

문제는 내가 현재 가지고 있는 서로 다른 길이의 랜선들을 잘라서 동일한 길이의 새로운 랜선을 여러개 만드는 것이다.

내가 가지고 있는 랜선의 개수 K와 새로 만들 랜선의 개수 N을 입력받는다.

예를 들어 K=4, N=11 이라면 4개의 긴 랜선을 잘라 11개의 짧은 랜선을 만드는 것이다.

이 때, 11개를 만들 수 있는 랜선의 최대 길이를 구하면 된다.

즉, 11개를 만들기 위해서 랜선을 얼마나 잘라야 하는지를 알면 된다.

정답으로 200을 출력한다면 가지고 있는 4개의 랜선으로 새로운 랜선 11개 만들 때 이 새로운 랜선의 최댓값이 200이 된다는 말이다.

문제에서 주어진 랜선의 길이는 2^31 - 1보다 작거나 같은 자연수 이기 때문에 절대 앞에서 부터 하나씩 값을 검사하는 순차탐색으로는 시간내에 해결할 수 없다.

그래서 이진탐색(Binary Search)을 이용하였다.

내가 가지고 있는 랜선의 길이의 합을 end값으로, 0을 start값으로 설정하여 이 두 값의 절반을 mid값으로 설정한 후, 탐색을 하면 된다. 0과 1600이라면 800부터 검사를 시작하여 문제를 해결해 나가면 된다.

순차탐색보다 훨씬 시간도 줄어들고, 시간 초과 문제도 해결할 수 있다.

코드는 다음과 같다.

k, n = map(int, input().split())
lan = []

maxcm = 0


def binary_search(array, target, start, end):
    while start <= end:
        moksum = 0
        mid = (start + end) // 2
        if mid == 0:
            return start        # 0값을 나누는 예외상황 처리
        for i in array:
            mok = i // mid
            moksum += mok
        if moksum < target:  # 개수를 더 늘려야 하므로 길이를 줄이자
            end = mid - 1
        elif moksum >= target:  # 개수를 더 줄일 수 있으므로 길이를 늘리자
            start = mid + 1

    return end


for i in range(k):
    lan.append(int(input()))

lansum = sum(lan)  # 입력받은 모든 랜선 길이의 합


result = binary_search(lan, n, 0, lansum) # 길이 배열, 만들어야 하는 랜선수, 시작값, 끝값
print(result)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/3020

문제에 대한 자세한 설명은 위 링크에 기술 되어있다.

쉽게 풀어쓰자면 동굴의 길이(N)와 높이(H)를 입력받는다.

동굴은 석순과 종유석으로 구성되어 있는데, 석순은 아래에서 자라는 고드름 종유석은 천장에서 나는 고드름이라고 생각하면 된다. 

문제에서 동굴의 길이만큼 석순과 종유석의 길이를 입력받는데, 번갈아 가면서 입력받는다. ( 석순과 종유석은 각각 동굴의 길이 1만큼 차지한다)

예를 들어, 1 3 4 2 5 6 이라고 입력했으면 석순 1, 4, 5 / 종유석 3 2 6 이 되는 것이다.

이렇게 장애물이 설치된 동굴에 개똥벌레 한마리가 날라가는데 동굴의 높이가 6일 때, 개똥벌레가 날아가는 높이가 3이라고 한다면 아래에서부터 높이 2~3 (2.5라고 생각하면 쉽다) 구간을 날라간다. 

그래서 3보다 낮은 석순에는 모두 부딪히게 되고, 3보다 큰 종유석에는 모두 부딪히게 된다. ( 위에서 부터 4 만큼 내려온 종유석에는 아래에서 부터 2.5만큼 날아오른 개똥벌레가 부딪히기 때문)

이런 상황에서 문제에서 최종적으로 구하고자 하는 것은, 개똥벌레가 파괴해야 하는 장애물의 최소 개수와 이 최소값이 나오는 구간의 수를 구하는 것이다.

그렇다면 어떻게 접근해야 할까?

가장 먼저 떠오른 방법은 석순과 종유석의 배열을 따로 두고, 각각의 배열을 정렬 한 후에 처음 개똥벌레가 부딪히기 시작한 높이를 계산하는 방식이다. 왜냐하면 그 이후의 구간은 모두 부딪힌다는 이야기가 되기 때문에 첫 구간만을 구해 그 구간 전까지의 개수를 통해 답을 구할 수 있기 때문이다. 이러한 접근 방식을 누적 합(또는 구간합)이라고 하는데

현재 페이지에서는 다른 방식으로 풀어보려고 한다.

바로 이진탐색(Binary Search) 방식으로 풀려고 한다.

석순과 종유석의 배열이 각각 정렬되어 있기 때문에, 배열의 중간지점에서 개똥벌레가 부딪히는지 테스트를 진행한다.

보통의 이진탐색 과정과 마찬가지로 start값과 end값에 변화를 주며 mid값을 조정하여 개똥벌레가 최소한으로 부딪히는 구간을 찾으면 된다.

코드는 다음과 같다.

n, h = map(int, input().split())

down = []
up = []
for i in range(n):
    if i % 2 == 0:
        down.append(int(input()))
    else:
        up.append(int(input()))

down.sort()
up.sort()

min_count = n
range_count = 0


def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start


for i in range(1, h + 1):
    down_count = len(down) - binary_search(down, i - 0.5, 0, len(down) - 1)
    top_count = len(up) - binary_search(up, h - i + 0.5, 0, len(up) - 1)

    if min_count == down_count + top_count:
        range_count += 1
    elif min_count > down_count + top_count: # 현재 범위가 새로운 최소 값이면
        range_count = 1
        min_count = down_count + top_count

print(min_count, range_count)

binary_search함수의 target은 개똥벌레의 높이가 되며 down일 때는 i - 0.5, up일때는 h - i + 0.5를 넣는다.

위에서 자라는 종유석의 경우에는 아래와는 반대로 생각해야 하기 때문이다.

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/10815

이 문제는 내가 입력한 숫자들이 상근이가 가지고 있는 숫자들에 존재하는지 확인하는 문제이다.

변수 n은 상근이의 숫자 카드 개수, card 는 그 카드들의 숫자 목록이다.

m은 내 카드 개수, check는 내 카드들의 숫자 목록이다.

즉 check의 요소들이 card에 존재 하는가를 검사 하면 된다.

이렇게 요소들을 확인하는 문제는 이진탐색(Binary Search) 문제라고 생각하면 쉽다.

요소가 엄청 작은 문제가 아닌 이상, 순차 탐색은 시간초과가 나오기 때문에 이분 탐색을 이용하자.

코드는 다음과 같다.

import sys

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort()

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


for i in range(m):
    if binary_search(card, check[i], 0, n - 1) is not None:
        print(1, end=' ')
    else:
        print(0, end=' ')

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/2110

문제에서 주어진 대로, N개의 집에 C개의 공유기를 설치한다.

이 때, 가장 인접한 두 공유기 사이의 거리가 최대 가 되도록 해야 한다.

즉, 집의 좌표가 [ 1, 2, 4, 8, 9 ] 이고 공유기를 3개 설치 할 때, 공유기를 1, 4, 8 혹은 1, 4, 9 에 설치를 해야

가장 인접한 두 공유기 사이의 거리(1, 4)가 3이 되고, 이 3 보다 작게 설치를 할 수는 없다.

그렇다면, 공유기를 설치해야 될 집은 어떻게 찾아야 할까?

가장 간단한 방법으로는 순차 탐색으로 앞에서 부터 일일이 설치 집을 탐색해보며 실행하는 방법이 있지만,

가장 비효율적인 방법이며 분명 시간 제한 오류가 난다.

이러한 탐색 문제를 가장 빠르게 푸는 방법은 바로 이진 탐색(Binary Search) 이다.

이진 탐색을 쉽게 설명하자면,

예를들어, 1 부터 100까지의 숫자 사이에서 랜덤으로 정해진 숫자 하나를 맞추는 게임을 한다고 하자.

이 때 내가 부를 수 있는 숫자의 횟수는 3회이며, 숫자를 외칠 때 마다 정답이 그 숫자보다 작은지 큰지 맞는지 확인할 수 있다. 랜덤으로 정해진 숫자는 80이고, 나는 이 정답을 모르는 상태라고 가정하자.

처음엔 당연히 절반인 50을 부르는게 좋을 것이다. 이 때 정답이 50보다 크기 때문에 출제자는 50보다 크다고 알려 줄 것이며 그 다음에는 50보다 작은 부분은 검사할 필요가 없다. 그래서 그 다음엔 50과 100의 절반인 75를 부른다.

만약 75보다도 크다면 또 75보다 작은 부분은 검사할 필요가 없다.

이런 식으로 절반 씩 쪼개가며 탐색할 부분을 좁혀가는 방법이다.

만약 순차 탐색으로 진행했다면 1부터 80까지 80번을 실행해야 하지만, 이진 탐색을 실행하면 불과 5회 정도 만에 답을 찾아낼 수 있는 것이다.

이 방법으로 문제를 진행해보면

1. array라는 리스트에 집들의 좌표를 입력받은 후에 정렬.

2. start = 1, end = array[-1] - array[0] 으로 설정. ( 시작값은 최소 거리, 끝 값은 최대 거리 )

3. 앞 집부터 공유기 설치

4. 설치할 수 있는 공유기 개수가 c개를 넘어가면 더 넓게 설치할 수 있다는 이야기 이므로 설치거리를 mid + 1로 설정하여 다시 앞집부터 설치.

5. c개를 넘어가지 않는다면 더 좁게 설치해야 한다는 이야기 이므로 mid - 1로 설정.

위의 과정을 반복실행하면 정답을 얻을 수 있다.

코드는 다음과 같다.

n, c = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !