[Programmers 코딩테스트 고득점 Kit] 구명보트

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

투 포인터를 이용하는 그리디 알고리즘 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 이인용 보트이기 때문에 최대한 짝을 맞춰서 보내야 합니다.

2. 즉, {그나마 가벼운 사람, 그나마 무거운 사람} 페어로 보내야 최대한 많은 짝을 이룰 수 있습니다.

3. 따라서, 몸무게를 기준으로 정렬을 진행한 뒤, 하나의 포인터는 가벼운 사람부터, 다른 포인터는 무거운 사람부터 시작하여 해당 포인터의 위치가 역전될 때까지 짝을 맞춰나갑니다.

4. 3번 과정을 거친 뒤 짝을 못 맞춘 사람은 어쩔 수 없이 한 명씩 타야 합니다.

5. 3번과 4번 과정에서 얻은 탑승 횟수를 반환합니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~