https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머
코드 중심 개발자를 모집합니다. 스택 기반 위치 일치. 프로그래머의 개발자별 프로필에 등록하고 귀하와 기술 호환성이 좋은 회사와 연결하십시오.
Programmers.co.kr
1. 내가 쓴 솔루션
이진 검색을 사용할 수 있습니까? 라고 생각했지만 2점슛을 사용했습니다.
1. 사람들을 무게별로 분류합니다.
2. 무게 값이 제한 무게 값보다 크면 해당 위치에서 끝까지 완전히 제외됩니다.
(문제의 조건은 구제불능의 경우가 별로 없다는 것입니다 ㅎㅎ)
3. 시작과 끝을 이동하고 각 2인의 인원수를 확인합니다.
– 시작은 사람 중 무게가 가장 적은 사람을 말하며, 끝은 무게가 가장 큰 사람을 말합니다.
– 사람(시작) + 사람(종료)이 제한 이하일 경우 끝에서 2명이 탑승할 수 없음을 의미합니다.
– 따라서 끝을 앞으로 이동합니다(체중이 적은 사람을 가리키도록).
4. 3번 과정을 반복한 후 start+end가 limit 이하가 되면,
– 사용 구명보트(cnt) 1개 증가
– 남은 인원을 2명으로 줄인다(2명이 구조되었기 때문에)
– 시작과 끝을 이동합니다.
5. 시작이 끝보다 크면 두 사람이 탈 수 있는 사건에 대한 조사가 끝난다.
– 따라서 남은 인원은 구명보트의 제한 중량보다 적지만 혼자 타야 하는 경우입니다.
– cnt(현재 사용 중인 구명정의 수) + 혼자 타야 하는 사람의 수를 반환합니다.
def solution(people, limit):
people = sorted(people)
number = len(people)
cnt = 0
start = 0
end = len(people)-1
while start < end and number!=0:
#제일 작은 값과 제일 큰 값이 limit보다 크면 end를 이동시켜줌
if people(start) + people(end) > limit:
end -= 1
#limit보다 작으면 구명보트의 개수 +=1, start와 end 이동해서 제일 큰 값과 작은 값 갱신
#남아 있는 사람 2명 적어짐
else:
cnt+=1
number -= 2
start+=1
end-=1
#남아있는 사람은 같이 탈 수 없는 사람이라 1개의 구명보트가 필요함
#2명씩 태운 구명보트(cnt) + 1명 태운 구명보트(number)
return cnt + number
3. 수정
def solution(people, limit):
people = sorted(people)
cnt = 0
start = 0
end = len(people)-1
while start <= end:
if people(start) + people(end) > limit:
end -= 1
cnt+=1
else:
cnt+=1
start+=1
end-=1
return cnt
비슷한 방법이라도 좀 더 쉽게 풀 수 있는 방법이 많은 것 같습니다.