문제 설명
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
변수 설명
- n
- 타입 : 정수
- 저장 데이터 : 로프의 개수를 저장합니다.
- rope
- 타입: 리스트
- 저장 데이터 : 로프가 들수있는 중량을 저장합니다. [ 다수 입력 ]
- weight
- 타입: 리스트- 저장 데이터 : 반복문을 통해 각 상황마다 들 수 있는 최대무게를 저장
풀이과정
- 로프의 개수를 입력 받는다. (n)
- 각 로프마다 버틸 수 있는 최대 중량을 입력 받는다. (rope)
- 내림차 순으로 무게를 정렬해준다.
- n 만큼 반복을 하며 rope[i] * (i + 1) 의 값을 weight에 저장해준다. (weight)
- max 메소드를 통해 weight 중 가장 큰 값을 출력한다.
코드
import sys
n = int(input())
rope = [int(sys.stdin.readline()) for i in range(n)]
rope.sort(reverse=True)
weight = [rope[i] * (i + 1) for i in range(n)]
print(max(weight))
배운점
처음 코드를 작성할 때에는 여러줄, 한줄 입력 모두 input으로 받고 실행하였다.
그러자 시간이 무려 4086ms 가 나왔을 정도로 오래걸렸다.
그래서 속도를 조금더 빠르게 하고자 방법을 찾았고, 여러 줄을 입력받을 때에는 input 보다는
sys.stdin.readline() 을 사용하는게 더 빠르다고 하여 관련 자료를 찾아보았다.
Input과sys.stdin.readline의 속도차이 원인!
-
input()내장 함수는parameter로prompt message를 받을 수 있다.
물론prompt message를 사용하지 않을때도 있지만, 사용하지 않아도 속도에 부하를 준다고 한다. 하지만,sys.stdin.readline()은prompt message를 인수로 받지 않는다. -
또한,
input()내장 함수는 입력받은 값의 개행 문자를 삭제시켜서 리턴한다.
즉 입력받은 문자열에rstrip()함수를 적용시켜서 리턴한다.
반면에sys.stdin.readline()은 개행 문자를 포함한 값을 리턴한다.
그래서 코드를 input이 아닌 sys.stdin.readline() 으로 입력을 받아서 코드를 다시 작성하였고
위 사진 처럼 속도가 획기적으로 줄어들었다!!
무려 20배가 넘게 줄어든 만큼 정말 문제를 풀 때 알고있는 사람과 모르는 사람의 속도차이가 엄청 심하다는걸 느낄 수 있었다.
그래서 욕심이 나서 더 코드를 빠르게 할 수 있는 방법을 찾다가 append 를 해주는 것보다 list comprehension 을 통해 list를 만들면 속도가 더 빠르다는것을 듣고 코드를 또 수정하였다.
그래서 기존 코드를 for문에서 append를 하는 방식에서 list comprehension을 통해 list를 만들자 또 다시 아래 사진처럼 속도가 줄어드는것을 알 수 있었다!
이번에 배운걸 토대로 다음번 문제를 풀때는 한번에 최적의 속도를 찾아 풀도록 해봐야겠다 :)
