랜선 자르기

생성일: 2022년 1월 14일 오후 5:27

구현 코드

# 랜선 자르기 (결정 알고리즘)
import sys
sys.stdin = open("input.txt", "rt")
k, n = map(int, input().split())
l = [int(input()) for _ in range(k)]
l.sort()
a = sum(l) // n
res = 0

while True:
    for x in l:
        res += x//a
    if res < n:
        a -= 1
        res = 0
    else:
        break

print(a)

모범 답안

# 랜선 자르기
import sys
#sys.stdin = open("input.txt", "rt")

def Count(len):
    cnt = 0
    for x in l:
        cnt += x//len
    return cnt

k, n = map(int, input().split())
l = []
largest = 0
for _ in range(k):
    tmp = int(input())
    l.append(tmp)
    largest = max(largest, tmp) # 가장 큰 수 찾기

lt = 1
rt = largest

while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid) >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

차이점

• 내가 구현한 코드는 입력 데이터가 많을때(k가 클 때) 실행 시간이 매우 길어진다.
• 반면 모범 답안에서는 Binary Search를 이용하여 범위를 절반으로 줄여가며 탐색을 하기 때문에 효율적이다.
• .txt 파일에서 숫자들을 불러와 리스트에 넣고, 해당 리스트를 정렬하여 가장 큰 수를 찾는 것 보다는 모범 답안처럼 .txt 파일에서 반복문으로 불러오는 과정에서 가장 큰 값을 갱신하며 찾는 것이 효율적이다.