🧮 [프로그래머스] 구명보트 (JAVA)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

문제 이해 && 풀이

문제이해는 굉장히 간단하다.

limit이 정해져 있고 그 limit에 맞게 가장 조금 움직인다. 라는 것이 다인데 중요한것은 어떻게 최적의 수를 구하는 것인가가 중요한 문제이다.

 

1. 밑에서 부터 계산했었던 실수

우선 처음으로 생각했던건 정렬 후에 가장 작은 수를 합해서 limit보다 작으면 두개를 제거 한다에 집중했다. 심지어 Queue를 사용해보았다. 하지만 이것은 다른 경우의 수에서 완전히 엉망이 되었다.

 

만약 수를 이렇게 준다면

50, 70, 50, 80 에 limit을 130 으로 바꿔주면 최소로 움직일 값이 50과70, 50과 80 으로 2번에 되는데 가장 작은 순으로 더해버리면 3번이 되기 때문에 잘못된 설계가 되는 것이다.

 

그래서 이것은 매우 잘못된 설정이기 때문에 다르게 생각해보았다.

 

 

2. 정답이 나오기 까지

우선 정렬을 하는 것은 맞다. ArrayList를 사용해서 remove하고 이런것도 생각해봤지만 시간 복잡도가 더욱 복잡해지고 엉망이 될 것 같았다. 그렇게 고민을 깊게 하는 과정에 찾은 중요한 것을 찾았다.

굳이 숫자를 지울 필요가 없다, limit의 제한 안으로 최소의 수와 최대의 수를 찾기

그냥 지나가고 다시 안가게 하면 되는 것이다. 이것을 기준으로 최소의 수를 더라고 최대의 수를 더하면 최소의 수를 찾게 되는 것이다.

 

소스코드

설명이 살짝 필요하다. 

1. sort를 이용해서 순서를 잡아주어야 한다
2. 반복문에 가장 마지막 수부터 시작하고 한칸씩 뒤로 가면서 찾아본다.
3. 만약 없다면 맨 뒤에 있는 수를 빼서 answer를 1 증가시키고 만약 더한 수가 limit을 넘지 않는다면 가장 작은수와 현재 가장 큰 수를 더해준다.
4. 그리고 가장 작은 수를 한칸 더 증가시킨다. 
5. 중요한것은 i >= min인데 감소하고 있는 최대의 수가 min을 넘어가면 안된다.

이런식으로 한번 지나간 수는 다시 안가게 되면서 굳이 지우지 않아도 문제를 풀 수 있다는 사실을 한번 더 깨닳았다