오늘의 공부

programmers.co.kr/learn/courses/30/lessons/42885

사실 결국 처음 고민했던 개념이 맞았다. 처음 값과 끝 값을 비교하면 됐다. 근데 굳이 erase를 할 필요없이 전에 풀었던 투 포인터 방식처럼 lidx와 ridx로 풀어줬더니 효율성까지 통과했다.

안에 for문도 써줄 필요가 없었다.

int solution(vector<int> people, int limit) {
	int answer = 0;
	sort(people.begin(), people.end()); // 정렬 
    
	// 제일 무거운사람하고 제일 가벼운 사람 태우기
	int lidx = 0;
	int ridx = people.size() - 1;
	while (lidx <= ridx)
	{
		if (people[lidx] + people[ridx] <= limit)
		{
			answer += 1;
			lidx += 1;
			ridx -= 1;
		}
		else if(people[lidx] + people[ridx] > limit){
			ridx -= 1;
			answer += 1;
		}

	}
	
	return answer;
}

해결하지 못했을 때 했던 고민들 ↓ 

효율성 테스트 4,5번은 맞는데 1,2,3번은 통과하지 못했다.

vector를 중간에 삽입,삭제 하면서 효율성이 떨어져서 그런가? 뭐가 문제일까..

보면 자꾸 효율성 검사 1,2,3번이 틀리는 경우가 좀 많은 것 같다. 테스트 케이스를 알면 어떤 부분을 잘못 생각하고 있는지 알 수라도 있을 것 같은데 프로그래머스는 이런 부분이 좀 아쉽다.

효율성 만점은 아니지만 생각했던 방법은 우선 사람들의 무게를 오름차순으로 정렬한 후에 

처음 값(제일 가벼움)과 마지막 값(제일 무거움)을 더한 값이 limit보다 큰 지, 작은지를 확인했다. 

만약 limit를 넘는다면 뒷 부분부터 앞으로 오면서 처음의 값과 비교했다.

그 후에 limit보다 작은 값을 찾게 됐다면 erase를 해줬는데 erase는 삭제 되면 capacity까지 줄어드니까

한 번 while문을 돌 때마다 다시 people 벡터의 size를 계산해주었다. 

그 후에 다 비교해봤는데 limit보다 작은 조합을 못찾았다면 이제 더이상 두 명씩 태울 수 없으므로 (cantTake == true) 남은 people 벡터의 사이즈만큼을 answer에 더해주고 반복문을 끝낸다. 

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    while(1)
    {
        bool cantTake = true;
        int people_cnt = people.size();
        if(people_cnt == 1)
        {
            answer += 1;
            break;
        }

        for(int i=people_cnt-1;i> 0 ; --i)
        {
            if(people[0] + people[i] <= limit)
            {
                cantTake = false;
                answer +=1;
                people.erase(people.begin() + i);
                people.erase(people.begin());
                break;
            }
        }
        if(cantTake)
        {
            answer += people_cnt;
            break;
        }
    }
    return answer;
}