[Python]프로그래머스 코딩테스트 연습 구명보트

programmers.co.kr/learn/courses/30/lessons/42885

 

문제는 이렇다. 최대 2명이 탈 수 있는 구명보트가 있고 무게제한이 있을때, 보트가 이동하는 최소한의 횟수를 알아내는 문제이다.

 

생각나는대로 짜본 코드. people을 무게순으로 오름차순 정렬하고 가장 무거운 사람이 가장 가벼운 사람과 같이 탈 수 있으면 타고 가고, 못 타면 혼자서 타고간다고 생각해서 짜보았다.

만약 남은 사람이 한명이라면 answer에 1이 더해지면서 종료.

채점결과 알고리즘은 맞지만 효율성에서 문제가 발생했다.

아무래도 while문 내에서 반복되는 요소들 때문에 효율성이 떨어져 있었다.

 

그래서 좀 더 효율적으로 수정해보았으나 역시 시간초과 ㅠㅠ

통과는 못했지만 기존 코드보다 효율적이긴 하다 ㅋㅋ

pop(), pop(0), people[0]을 사용했기 때문에 시간복잡도가 적다고 생각했는데 효율성 통과가 생각보다 빡셌다.

결국 pop을 사용하는것 자체가 효율성이 떨어지고 있었다.

 

그래서 sort한 후에 가장 작은것 people[i] 과 people[j]를 비교하게 하면서 해결해야 했다.

만약 두 사람의 합이 무게를 초과하지 않으면 가장 작은 수는 한칸 뒤로 j는 한칸씩 앞으로 오면서 진행된다.

두 사람의 합이 무게를 초과한다면 그냥 j만 한칸씩 앞으로 온다(가장 무거운 사람만 타고감).

리스트 원소를 제거하지 않고 그냥 비교하니까 더 효율적으로 나왔다.

그 전에는 pop(0) 이나 pop()은 시간복잡도가 거의 발생하지 않는다고 인식해왔었는데 pop이라는 기능 자체로 인해 효율성이 떨어지는건 생각하지 못했었다. pop하면서 원소를 다시 이용하고, 리스트 또한 갱신이 되어야 하기 때문인듯 하다.

특히 테스트 3번에서 엄청난 효율을 보여줬다. 많은 공부가 되었던 연습문제였다.