탐욕법(Greedy)
구명보트
1차 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
sort(people.begin(), people.end());
while (people.size()) {
int most_heavy = *--upper_bound(people.begin(), people.end(), limit);
people.erase(--upper_bound(people.begin(), people.end(), limit));
if (people.size()) {
auto second_most_heavy = --upper_bound(people.begin(), people.end(), limit - most_heavy);
if (second_most_heavy != --people.begin()) people.erase(--upper_bound(people.begin(), people.end(), limit - most_heavy));
}
answer++;
}
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.46ms, 3.92MB) 테스트 2 〉 통과 (0.27ms, 3.91MB) 테스트 3 〉 통과 (0.34ms, 3.94MB) 테스트 4 〉 통과 (0.29ms, 3.93MB) 테스트 5 〉 통과 (0.16ms, 3.95MB) 테스트 6 〉 통과 (0.09ms, 3.89MB) 테스트 7 〉 통과 (0.13ms, 3.88MB) 테스트 8 〉 통과 (0.02ms, 3.89MB) 테스트 9 〉 통과 (0.03ms, 3.96MB) 테스트 10 〉 통과 (0.30ms, 3.89MB) 테스트 11 〉 통과 (0.29ms, 3.9MB) 테스트 12 〉 통과 (0.25ms, 3.93MB) 테스트 13 〉 통과 (0.29ms, 3.95MB) 테스트 14 〉 통과 (0.31ms, 3.95MB) 테스트 15 〉 통과 (0.03ms, 3.84MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 통과 (4.91ms, 4.68MB) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 통과 (4.84ms, 4.82MB) 테스트 5 〉 통과 (4.23ms, 4.56MB) 채점 결과 정확성: 75.0 효율성: 15.0 합계: 90.0 / 100.0
2차 시도
#include <string>
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
multiset <int> weight(people.begin(), people.end());
weight.insert(-1);
while (weight.size() > 1) {
auto most_heavy_iter = --weight.lower_bound(limit + 1);
int most_heavy = *most_heavy_iter;
weight.erase(most_heavy_iter);
if (weight.size() > 1) {
auto second_most_heavy = --weight.lower_bound(limit - most_heavy + 1);
if (*second_most_heavy != -1) weight.erase(second_most_heavy);
}
answer++;
}
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.94ms, 3.86MB) 테스트 2 〉 통과 (0.62ms, 3.87MB) 테스트 3 〉 통과 (0.65ms, 3.89MB) 테스트 4 〉 통과 (0.60ms, 3.96MB) 테스트 5 〉 통과 (0.35ms, 3.95MB) 테스트 6 〉 통과 (0.19ms, 3.91MB) 테스트 7 〉 통과 (0.31ms, 3.91MB) 테스트 8 〉 통과 (0.04ms, 3.95MB) 테스트 9 〉 통과 (0.06ms, 3.71MB) 테스트 10 〉 통과 (0.62ms, 3.89MB) 테스트 11 〉 통과 (0.52ms, 3.98MB) 테스트 12 〉 통과 (0.46ms, 3.97MB) 테스트 13 〉 통과 (0.63ms, 3.93MB) 테스트 14 〉 통과 (0.72ms, 3.94MB) 테스트 15 〉 통과 (0.07ms, 3.93MB) 효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과) 채점 결과 정확성: 75.0 효율성: 0.0 합계: 75.0 / 100.0
3차 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
sort(people.begin(), people.end(), greater<>());
for (int left=0, right=people.size()-1; left<=right; left++) {
if (people[left] + people[right] <= limit) {
right--;
}
answer++;
}
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.17ms, 3.94MB) 테스트 2 〉 통과 (0.11ms, 3.96MB) 테스트 3 〉 통과 (0.13ms, 3.91MB) 테스트 4 〉 통과 (0.12ms, 3.95MB) 테스트 5 〉 통과 (0.08ms, 3.95MB) 테스트 6 〉 통과 (0.04ms, 3.92MB) 테스트 7 〉 통과 (0.06ms, 3.89MB) 테스트 8 〉 통과 (0.01ms, 3.96MB) 테스트 9 〉 통과 (0.02ms, 3.93MB) 테스트 10 〉 통과 (0.11ms, 3.97MB) 테스트 11 〉 통과 (0.11ms, 3.83MB) 테스트 12 〉 통과 (0.10ms, 3.97MB) 테스트 13 〉 통과 (0.11ms, 3.94MB) 테스트 14 〉 통과 (0.12ms, 3.94MB) 테스트 15 〉 통과 (0.02ms, 3.84MB) 효율성 테스트 테스트 1 〉 통과 (1.67ms, 4.66MB) 테스트 2 〉 통과 (1.43ms, 4.63MB) 테스트 3 〉 통과 (1.42ms, 4.76MB) 테스트 4 〉 통과 (1.21ms, 4.79MB) 테스트 5 〉 통과 (1.21ms, 4.6MB) 채점 결과 정확성: 75.0 효율성: 25.0 합계: 100.0 / 100.0
섬 연결하기
1차 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<vector<int>> costs) {
int answer = -1;
vector<vector<int>> field(n, vector<int> (n, -1));
vector<int> road;
for (auto a:costs) {
field[a[0]][a[1]] = a[2];
field[a[1]][a[0]] = a[2];
}
for (int i=0; i<n; i++) road.push_back(i);
do{
int score = 0;
bool isRoad = true;
for (int i=0; i<n-1; i++) {
if (field[road[i]][road[i+1]] == -1) {
isRoad = false;
break;
}
score += field[road[i]][road[i+1]];
}
if (isRoad && (answer == -1 || answer > score)) {
answer = score;
}
} while (next_permutation(road.begin(), road.end()));
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.01ms, 3.9MB) 테스트 2 〉 통과 (0.01ms, 3.72MB) 테스트 3 〉 실패 (1.99ms, 3.89MB) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (0.27ms, 3.77MB) 테스트 6 〉 실패 (시간 초과) 테스트 7 〉 실패 (시간 초과) 테스트 8 〉 실패 (0.02ms, 3.96MB) 채점 결과 정확성: 25.0 합계: 25.0 / 100.0
2차 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
sort(costs.begin(), costs.end(), [] (vector<int> a, vector<int> b) {return a[2] < b[2];});
vector<vector<int>> choose_node = {costs[0]};
vector <int> parent;
for (int i=0; i<n; i++) parent.push_back(i);
parent[choose_node[0][1]] = parent[choose_node[0][0]];
for (int i=1; i<costs.size(); i++) {
if (choose_node.size() == n - 1) break;
if (parent[costs[i][0]] == parent[costs[i][1]]) continue;
choose_node.push_back(costs[i]);
parent[choose_node.back()[1]] = parent[choose_node.back()[0]];
}
for (vector<int> a:choose_node) {
answer += a[2];
}
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.01ms, 3.95MB) 테스트 2 〉 통과 (0.01ms, 3.96MB) 테스트 3 〉 실패 (0.02ms, 3.94MB) 테스트 4 〉 실패 (0.02ms, 3.97MB) 테스트 5 〉 실패 (0.02ms, 3.98MB) 테스트 6 〉 통과 (0.04ms, 3.72MB) 테스트 7 〉 실패 (0.04ms, 3.77MB) 테스트 8 〉 통과 (0.01ms, 3.96MB) 채점 결과 정확성: 50.0 합계: 50.0 / 100.0
3차 시도
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
sort(costs.begin(), costs.end(), [] (vector<int> a, vector<int> b) {return a[2] < b[2];});
vector<vector<int>> choose_node = {costs[0]};
vector <int> group;
for (int i=0; i<n; i++) group.push_back(i);
group[choose_node[0][1]] = group[choose_node[0][0]];
for (int i=1; i<costs.size(); i++) {
if (choose_node.size() == n - 1) break;
if (group[costs[i][0]] == group[costs[i][1]]) continue;
choose_node.push_back(costs[i]);
for (int i=0, change_group = group[choose_node.back()[1]]; i<group.size(); i++) {
if (group[i] == change_group) group[i] = group[choose_node.back()[0]];
}
}
for (vector<int> a:choose_node) {
answer += a[2];
}
return answer;
}정확성 테스트 테스트 1 〉 통과 (0.01ms, 3.98MB) 테스트 2 〉 통과 (0.01ms, 3.95MB) 테스트 3 〉 통과 (0.02ms, 3.95MB) 테스트 4 〉 통과 (0.02ms, 3.97MB) 테스트 5 〉 통과 (0.02ms, 3.77MB) 테스트 6 〉 통과 (0.06ms, 3.96MB) 테스트 7 〉 통과 (0.05ms, 3.89MB) 테스트 8 〉 통과 (0.01ms, 4MB) 채점 결과 정확성: 100.0 합계: 100.0 / 100.0
(ง ᐖ)ว