블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.본 글은 [ 백준 ] 2217번: 로프를 풀고 작성한 글입니다.
문제
설명
N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
풀이
접근법
주어진 로프를 내림차순 정렬한 다음 가장 큰수부터 1, 2, 3 ... N개까지 순서대로 곱해서 가장 큰 수를 출력하면 될 거라 생각했다.
이때 유의할 점은 순서대로 곱하는 과정을 for 반복문을 통해서 수행할 때 이미 정렬이 되어 있는 것을 대상으로 반복문을 돌리지 않으면 반복문 내부에서 정렬을 해야 하기 때문에 복잡도가 O(n^2)을 초과할 수 있다는 것이다. 따라서 반드시 for 반복문을 수행하기 이전에 내림차순 정렬을 해줘야 한다.
나의 풀이
접근법을 토대로 아래와 같이 내장 함수 sort() 를 사용하였는데 reverse 매개변수의 값을 True 로 하여 내림차순 정렬하였다. 이때 또다른 내장함수 enumerate() 를 사용하여 리스트의 요소와 함께 인덱스도 반환받았다.
한 가지 특이한 사항으로는 answer 변수에 비교 이후 조건을 충족하면 값을 바로 대입해주기 위해 왈루스 연산자(Wallus Operation)를 사용하여 비교 구문에 current_weight 변수를 선언한 것이다.
N: int = int(input())
ropes: list[int] = [ int(input()) for _ in range(N) ]
ropes.sort(reverse=True)
answer: int = ropes[0]
for idx, weight in enumerate(ropes):
if (current_weight := weight * (idx + 1)) > answer:
answer = current_weight
print(answer)아래와 같이 리스트 컴프리헨션 및 sorted(), enumerate(), 그리고 max() 내장함수를 활용하여 짧게 문제를 해결할 수 있다.
N: int = int(input())
ropes: list[int] = [ int(input) for _ in range(N) ]
print(max([ weight * (idx + 1) for idx, weight in enumerate(sorted(ropes)) ]))Big-O
파이썬 내장 함수 sorted() 의 시간 복잡도가 O(NlogN)이기 때문에 for 반복문에서 배열의 길이 N 만큼, 다시 말해 O(N)의 시간 복잡도가 들더라도 정렬 때문에 결국 Big-O는 O(NlogN)이다.
