[python] 2217, 로프

[문제]

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

 

[입력]

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

 

[출력]

첫째 줄에 답을 출력한다.

 

[예제]

 

[풀이]

• 기본 아이디어
  • Ex. 10, 20, 30 의 로프 3개가 있을 때 (10, 10, 10 = 30), (20, 20 = 40), (30 = 30) 의 세가지 경우의 수가 가능함
  • 모든 로프의 최대 중량을 리스트에 담은 뒤 오름차순으로 정렬하면
  • 리스트의 첫번째 원소는 모든 로프 중 버틸 수 있는 가장 적은 중량을 나타내기 때문에 리스트 내의 모든 원소들이 해당 중량을 버틸 수 있음 -> 따라서, 첫번째 원소가 버틸 수 있는 "최대 중량 X 리스트 원소 총개수"를 해주면 됨
  • 같은 원리로 그다음 원소들에 대해서도 해당 원소의 최대 중량값에 해당 원소 이후에 있는 원소의 개수만큼 곱해주면 모든 경우의 수를 구할 수 있음
    • Ex. i번째 원소 : list[i] X (len(list) - i)
• 풀이1 - list 사용 : 시간 제일 많이 걸림 제일 짧았던 코드보다 30% 정도 느림

n = int(input())
rope = []
result = []

for _ in range(n):
  rope.append(int(input()))

rope.sort()

for i in range(len(rope)):
  result.append(rope[i] * (len(rope) - i))

print(max(result))

• 풀이2 - list 미사용 : for문을 반복하며 result라는 변수에 저장한 값보다 큰값이 등장했을 때 result 변수값을 업데이트

n = int(input())
rope = []
maxx = 0

for _ in range(n):
  rope.append(int(input()))

rope.sort()
rope_num = len(rope)

for i in range(rope_num):
  result = rope[i] * (rope_num - i)
  if maxx < result:
    maxx = result

print(maxx)

• 알게된 점
  • 원래는 rope_num을 len(rope)이렇게 써서 사용했었는데
  • 생각보다 len()과 같은 내장함수의 시간 소모율이 크다는 것을 알게됨
  • 풀이1이 코드는 더 간단하지만, 계속 append함수를 호출하고, max함수를 사용하고 하다보니
  • 시간이 풀이2보다 훨씬 많이 걸렸음
  • 함수 사용을 최소화하는게 시간을 줄일 수 있겠다 생각했다 !