[Python-CodingTest] 4-2. 랜선 자르기 (결정 알고리즘)

랜선 자르기

문제 정리

입력

4 11 // k n
802 // 1번째 랜선
743 // 2번째 랜선
457 // 3번째 랜선
539 // 4(=k)번째 랜선

처리 과정

1. 랜선 리스트에서 가장 긴 랜선의 길이 구하기
2. 길이가 len인 랜선으로 잘랐을 때 몇개 나오는지 확인하는 함수(checkCount()) 작성
3. 처음과 끝을 가리킬 두 개의 포인터 생성(p1,p2)
4. while문 돌면서 mid 갱신
5. checkCount()>=n인 경우: 더 긴 길이가 있을 수 있으니 p1 갱신하고 계속 반복
6. checkCount()>=n인 경우: p2 갱신하고 계속 반복
7. while문 끝나면 res에 최댓값 저장되어 있음

출력

200

내 답

import sys
sys.stdin = open("./input/in2-1.txt", "rt")

# k: 이미 가지고 있는 랜선의 개수
# n: 필요한 랜선의 개수
k,n=map(int, input().split())
lst=[0]*k
for i in range(k):
    lst[i]=int(input())

# 랜선들을 특정 길이로 잘랐을 때 몇개가 나오는지 확인하는 함수
def checkCount(lst,len,k): # 파라미터: (랜선 리스트, 자른 랜선의 길이, 처음 가지고 있던 랜선 개수)
    cnt=0
    for i in range(k):
        cnt+=lst[i]//len
    return cnt

# 1 < 자른 랜선의 길이 < 802(랜선 리스트에서 가장 긴 랜선)
p1=1
p2=802

while p1<=p2:
    mid=(p1+p2)//2
    if checkCount(lst,mid,k)==n:
        print(mid)
        break
    elif checkCount(lst,mid,k)<n: # 개수가 너무 적게 나왔으니까 더 많이 나오도록 (자를)랜선의 길이를 줄이기
        p2=mid-1
    else: # 개수가 너무 많이 나왔으니까 더 적게 나오도록 (자를)랜선의 길이를 늘리기
        p1=mid+1

풀이

import sys
sys.stdin = open("./input/in2-1.txt", "rt")

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

lst=[] # 빈 (랜선)리스트
res=0 # 최댓값 
longest=0 # 랜선 리스트에서 가장 긴 랜선

for i in range(k):
    tmp=int(input()) # split()이 아니라 하나하나씩 input()으로 받아오기
    lst.append(tmp)
    longest=max(longest,tmp) # max(): 둘 중에 큰 값을 찾아주는 함수

# 길이가 len인 랜선으로 잘랐을 때 몇개 나오는지 확인하는 함수
def checkCount(len): # 파라미터로 lst와 k는 입력받을 필요 없음!
    cnt=0
    for x in lst:
        cnt+=x//len
    return cnt
    
p1=1
p2=longest

while p1<=p2:
    mid=(p1+p2)//2 # mid는 자른 랜선의 길이
    if checkCount(mid)>=n:
        res=mid # mid를 res에 담아두기
        p1=mid+1 # 더 최대인 길이를 찾아서 나감
    else:
        p2=mid-1

print(res) # res가 아닌 mid를 출력하면 200이 아니라 201이 나오니 주의!

정리

• 리스트에 값 하나씩 집어넣기: 빈 리스트(lst=[]) 만들어서 lst.append()
• max(a,b): a,b 중 더 큰 수를 반환
• n개를 만족하는 길이가 아닌, 최대 길이를 찾기 위해서 while문 끝까지 다 돌기
• mid를 출력하는게 아니라, mid를 res에 미리 담아두고 res를 출력!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기