나의 풀이
처음에 작성한 코드로 문제는 해결하였지만 효율성 검사에서 실패해서 수정을 계속하다가 코드가 꼬여버렸다.
아마도 for문 안에 erase함수를 넣었는데 O(n)의 함수이다 보니 실행속도가 느려진 것 같다.
이 코드를 살릴 바에는 새로운 로직을 생각해보면 어떨까 싶어서 원래 작성한 코드를 저장해놓고 다른 로직을 작성해봤는데 알고보니 엄청 간단한 문제였다.
먼저 주어진 스트링을 어렵게 설정해봤다.
people = {10, 30, 50, 60, 70, 80, 90, 100, 110, 120}, limit = 100이라고 가정하자
처음부터 정렬하기 때문에 순서는 상관없다.
i는 스트링의 제일 앞 j는 스트링의 제일 뒤부터 시작한다.
i+j가 limit보다 클 때 j를 1씩 감소하고 score를 1 증가한다.
10 + 120은 limit보다 크므로 j를 1 감소하고 score를 1 증가한다.
10 + 110은 limit보다 크므로 j를 1 감소하고 score를 1 증가한다.
10 + 100은 limit보다 크므로 j를 1 감소하고 score를 1 증가한다.
10 + 90은 limit보다 크지 않다. 이 때 j를 1 감소하고 i와 score를 1 증가한다.
30 + 80은 limit보다 크므로 j를 1 감소하고 score를 1 증가한다.
30 + 70은 limit보다 크지 않으므로 j를 1 감소하고 i와 score를 1 증가한다.
50 + 60은 limit보다 크므로 j를 1 감소하고 score를 1 증가한다.
i와 j가 같아지는 시점에 score를 리턴한다.
만약에 people에 50 하나가 더 있다면
i가 j보다 커진다. 이 때 ++score를 리턴한다.
🎉완성코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
//우선 정렬
sort(people.begin(), people.end());
int i = 0;
int score = 0;
for (size_t j = people.size() - 1; ; --j)
{
if (i == j) return ++score;
if (i > j) return score;
++score;
if (people[i] + people[j] > limit) continue;
++i;
}
}
추천을 많이 받은 풀이
이 사람도 나와 같은 방식으로 생각했나보다. 내 코드는 루프 안에 조건문이 3개 있어서 이 코드보다 대체로 시간이 조금 더 걸리는 것 같다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
sort(people.begin(), people.end());
reverse(people.begin(), people.end());
int N = (int)people.size();
int res = 0;
for (int i = 0, j = N - 1; i <= j; i++) {
if (people[i] + people[j] <= limit) {
j--;
}
res++;
}
return res;
}