프로그래머스: 구명 보트

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

프로그래머스

 

투포인터를 이용한 문제

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;int temp=0; int cnt=0;
    sort(people.begin(), people.end()); //오름차순 정렬
    //투포인터 사용하기
    int i=0; int j=people.size()-1;
    while(i<=people.size()-1 && j>=0){
        if(i>=j) break;
        if(people[i]+people[j]<=limit){
            people[i]=people[j]=0;
            answer++; i++; j--;
        }
        if(people[i]+people[j]>limit){
            j--;
        }
    }
    //짝지어지지않은 사람 배에 한명씩 태우기
    for(int p:people){
        if(p!=0) answer++;
    }
    
    // for(int i=0;i<people.size();i++){
    //     if(people[i]<0) continue;
    //     if(cnt==people.size()) break;
    //     temp=limit-people[i]; answer++; cnt++;
    //     for(int j=i+1;j<people.size();j++){
    //         if(people[j]<0) continue;
    //         if(people[j]<= temp){
    //           people[j]=-1; cnt++; break;  
    //         }  
    //     }
    // }
    return answer;
}

 

이중 for문을 돌리면 시간초과가 난다.

이때 투포인터를 사용하자. 투포인터는 맨 앞과 맨 뒤에 포인터를 하나씩 둬서 간 곳은 또 가지않고 맨 앞 포인터는 인덱스가 증가하는 방향으로만, 맨 뒤 포인터는 인덱스가 감소하는 방향으로만 움직인다.