[프로그래머스] 구명보트

무게 제한이 있고 최대 2명 태울 수 있는 보트의 최소 개수를 구하는 문제.

처음에는 무게순으로 정렬한 후에 투포인터로 해결하려 했으나 TLE가 나왔다. 제한사항을 잘 살펴보니 사람의 무게 범위는 40~240이라고 명시되어 있어서 굳이 정렬할 필요가 없었고 값의 하한과 상한 사이에서 투포인터를 사용하면 되는 거였다. 기존의 $O(NlogN)$보다 더 빠른 $O(N)$으로 구현했더니 통과가 되었다. 처음에는 계속 WA가 뜨길래 한참 헤맸었는데 혹시나 해서 하한을 40에서 0으로 낮추니까 통과가 되었다. 알고보니 명시된 제한사항과 다른 입력이 테스트케이스에 들어가 있었다.

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

cpp code

#include <vector>
#include <assert.h>

using namespace std;

int cnt[301];
int visit_cnt;

int solution(vector<int> people, int limit) {
	int answer = 0;

	for (int i : people) {
		cnt[i]++;
        //assert(i >= 40);
	}

	int l = 0, r = 240;
	while (l <= r) {
		if (cnt[l] == 0) {
			l++;
			continue;
		}
		if (cnt[r] == 0) {
			r--;
			continue;
		}
		if (l + r > limit) {
			r--;
		}
		else {
			if (l == r && cnt[l] < 2) break;
			cnt[l]--;
			cnt[r]--;
			answer++;
			visit_cnt += 2;
		}
	}

	answer += people.size() - visit_cnt;

	return answer;
}