이 문제는 for문으로 시작하면 오히려 더 헷갈린다.
중요한 건 몇 번 도느냐가 아니라, 한 번 판단했을 때 뭐가 확정되느냐였음
프로그래머스 구명보트 문제
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
오늘 구명보트 문제를 풀었다
문제를 보자마자 아무 생각 없이 for문 돌리면 되겠네 부터 떠올랐다
사람 수 많고, 조합을 보는 문제처럼 보였기 때문이다
물론 틀리게 되면서, 이번엔 스스로 약속을 했다.
천천히 하루에 하나씩! GPT한테 정답은 절대 묻지 말고 힌트만 받자!
당연하게도 중간중간 엄청 헤맸다.
for문을 또 당연시하게 쓰다가 꼬이고, 배열 자르다가 더 꼬이고, max, min을 사용도 해봄.
전환점은 이 생각이었다!
배는 매번 한 대씩 무조건 출발한다는 것.
한 번 판단하면, 그 배에는 1명이든 2명이든 타고 나가는 것
그리고 가장 무거운 사람도 결국 그 배를 탄다는 것
이 기준으로 보니까 for문으로 전부 훑을 필요가 없었다
앞에서 하나, 뒤에서 하나를 보면서 사람이 사라지는 방향으로 생각하는 게 훨씬 자연스러웠다
그래서 최종적으로 이렇게 풀었다
위 생각을 기준으로 정리하니, 코드도 훨씬 단순해졌다.
중요했던 건 사람을 전부 비교하는 것이 아니라
한 번의 판단으로 누가 사라지는지를 명확히 하는 거였다.
function solution(people, limit) {
let count = 0;
const arr = people.sort((a, b) => a - b);
let left = 0;
let right = arr.length - 1;
while (left <= right) {
// 가장 가벼운 사람 + 가장 무거운 사람을 먼저 태워본다
if (arr[left] + arr[right] <= limit) {
left++; // 같이 탈 수 있으면 가벼운 사람도 처리
}
// 가장 무거운 사람은 무조건 이 배를 탄다
right--;
count++; // 배 한 대 출발
}
return count;
}
이 코드에서 내가 중요하게 생각한 기준
- while 한 번 = 배 한 대
- 가장 무거운 사람은 매번 반드시 처리된다
- 가벼운 사람은 같이 탈 수 있을 때만 처리된다
- 배열을 자르지 않고, 포인터만 이동한다
이렇게 기준을 잡고 나니
for문으로 모든 경우를 보려던 생각이
오히려 불필요했다는 게 보였다.
이번 문제를 풀면서 느낀 건 이거다.
문제 보자마자 반복문부터 떠올리는 습관이
생각보다 사고를 많이 제한한다는 것.
다음부터는 코드를 쓰기 전에
“이 반복에서 뭐가 확정되지?”
이 질문부터 던져보려고 한다.