박은 캠프 때 n개의 랜선을 만들어야한다.
오에게 도움을 청했고, 오는 k개의 랜선을 가지고 있는데, 길이가 제 각각이다.
박은 랜선을 모두 n개의 같은 길이 랜선으로 만들고 싶다.
이때 최대 랜선의 길이를 구하는 프로그램을 만들어라.
알고리즘을 활용해야하는 문제 같다. 이진탐색 알고리즘을 사용하는 것으로 판단되지만, 일단 인간이 접근하는 방법을 토대로 풀어보고 싶었다.
1. 첫 번째 풀이 : 내 마음대로 풀이(테스트케이스 통과O but 시간 초과 코드)
그래서 우선은 나에게 수학적 문제로 주어졌다면 어떻게 풀 수 있을까 생각해봤다.
만약 k=n을 요구했다면, 당연히 가장 길이가 짧은 랜선의 길이가 result가 될 것이다.
그리고 실제로 인간의 감각(훈련된 수학적 사고)로 어떻게 하는지 생각해봤는데,
내림차순으로 lines를 정렬하고,
만약 k+1<=n가 시작되면
반복문은, 큰 수의 1/2부터 넣어보며, 몇 개의 조각이 나올 수 있는지 계산해본다.
그리고 가장 작은 수까지 반복문을 돌았는데 원하는 n에 접근되지 못하면,
큰수의 1/4부터 넣어보며, 전체에서 총 몇 개의 조각이 나올 수 있는지 계산한다.
이렇게 했을 때, 미세한 조정은 조금 더 필요하겠으나 대략적인 접근과 예제 입력은 만족시킬 수 있게 된다.
import sys, math
input=sys.stdin.readline
k, n= map(int, input().rstrip().split())
#k개의 랜선
#를 n개로 모두 같은 길이로 만드세요
#n개를 만들 수 있는 랜선의 최대 길이 출력
lines=[int(input()) for _ in range(k)]
lines.sort(reverse=True) #오름차순으로 정리
#lines는 내림차순 정렬 이후 건들이기 없기
cnt=0 #몇 번째 순회인지 확인
breaker1=False
breaker2=False
while(True):
if breaker1 == True and breaker2 == True: #삼중반복문 탈출
break
#밖에서 Lines를 변형해준다.
standard_lines = [math.floor(line*((0.5)**cnt)) for line in lines] #변경 가능한 조건
for standard in standard_lines: #line은 나누는 기준 line
#이중반복문 탈출
if breaker1==True:
breaker2=True
break
q_sum=0 #만들어지는 그룹의 개수
for line in lines:
q=line //standard
q_sum+=q
if q_sum == n:
print(standard)
breaker1=True
break
cnt+=1
그래도 바로 틀렸어요!가 아니라 시간초과가 떠서 그나마 기분이 좋다.
왜냐하면 종이에다가 쓰고, 블로그에다가 글을 쓰면서 계산하니까
술술 풀린 문제이고, 스스로도 뿌듯했기 때문이다.
반복문이 너무 많은 게 문제인 것 같아서
standard_lines를 매번 반복문으로 돌리는 부분을 좀 어떻게 해볼까 싶다.
해결하기가 쉽지 않아서, 카카오톡 오픈 채팅방에다가 물어보기도 했는데
이렇게 맞닿은 상황에서는, 로직 자체가 잘못된 경우에는 빠르게 바꾸는 것이 좋다고 한다.
2. 이진 탐색을 이용한 풀이
먼저 아직 이진 탐색 풀이에 익숙하지 않기 때문에, 이전에 풀었던 문제부터 복습해보겠다.
1920 수찾기 문제에서 풀었던 이진탐색 코드는 다음과 같다.
def binary_search(a_list, x):# a는 탐색 대상 리스트, 찾아야 하는 수 x
start=0
end=len(a_list)-1
while(start<=end):
mid=(start+end)//2
if a_list[mid] == x:
return 1
elif a_list[mid] < x:
start= mid+1
else: #a_list[mid] > x:
end = mid -1
return 0
최종적으로 작성한 코드는 다음과 같다.(정답 코드)
import sys
def input()->str:
return sys.stdin.readline().rstrip()
#이진탐색
def binary_search(a_list, x):# a는 랜선 리스트, x는 입력한 n
start=1 #가장 짧은 길이
end=a_list[-1] #가장 긴 길이
while(start<=end):
print('현재 start=',start,'현재 end=', end)
mid=(start+end)//2 #결국 최종적으로 mid가 문제에서 찾고자 하는 정답이 될 것임
result=0
print('현재 mid=',mid)
for line in a_list:
result+= line // mid
print('현재 result=',result)
if result >= x:
start = mid+1
elif result < x : #개수가 x보다 적으면,개수를 늘릴 수 있도록 해야하니까 정답인 mid를 더 작게 바꿔야한다.
end = mid -1
# else: #result > x: #개수가 x보다 많으면, 개수를 줄일 수 있도록 정답인 mid를 키운다.
# start= mid+1
return end
k, n = map(int, input().split())
#k개의 랜선을 n개로 모두 같은 길이로 만드세요
#n개 만들 수 있는 랜선의 최대 길이 출력(answer)
lines=[int(input()) for _ in range(k)]
lines.sort() #오름차순으로 정리
print(binary_search(lines, n))
처음에는 이분탐색 함수 내에서,
if result == x:
return mid
elif result > x:
start = mid + 1
else: #result < x:
end = mid -1
이렇게 조건문을 작성했다. 정답 코드에서는 end를 출력하는데, 내 오답에서는 mid를 출력했다.
약간은 이해가 덜 되긴 했는데, start가 아닌 mid인 이유는, 마지막에 start는 while문에서 조건식을 초과하기 때문에 end로 출력한 것이고, while문이 모두 끝나야 최선의 답을 찾을 수 있기 때문에, while문이 모두 끝난 뒤의 값을 출력하는 게 예외사항 없이 맞는 듯하다.
이진탐색(이분탐색)에 대해 확실히 공부할 수 있어서 좋은 문제였다.
+) 추가 공부 : 이중 반복문에서 break해서 나오는 방법
맨날 코드를 짜다가 이러한 상황에 마주해서 당황한 적이 많았는데, 한번 정리를 하고 가는게 맞는 것 같다.
1) 불린형 조건 활용
breaker = False로 기본값으로 주어주고, 첫 번째 반복문을 나올 때 breaker=True로 바꾸면서 break한다.
그리고 두 번째 반복문에서는 breaker가 True이면 정지하도록 걸어둔다.
2) 예외처리 try: except: 문 활용
try: 이중 반복문
except :
#오류 발생시 실행할 문구 작성
와 같이 코드를 짜면, NotImplementedError(선언되지 않은 에러)를 발생시켜, 다중 for문을 바로 종료시킨다.
그런데 이 방법보다는 1번 방법이 더 선호되는 것으로 알고 있다. 너무 많이 쓰면 가독성이 떨어지고, 코드 실행속도가 느려질 수 있기 때문!
이외 방법은 아래에서 참고 가능하다.
try:
# 예외 발생 가능한 코드
result = some_function()
except ValueError:
# ValueError 예외 처리
print("ValueError occurred")
except IndexError:
# IndexError 예외 처리
print("IndexError occurred")
except Exception as e:
# 그 외 모든 예외 처리
print("An error occurred:", e)
finally:
# 예외 발생 여부에 상관없이 실행되는 코드
print("Execution complete")
위 코드 블록 내용 출처 : https://twoicefish-secu.tistory.com/520