π νλ‘κ·Έλλ¨Έμ€ κ΅¬λͺ λ³΄νΈ CPP
π 첫 λ²μ§Έ νμ΄
- μ½λ μλ : μΌλ¨ μκ°λλλλ‘ λΉ¨λ¦¬ νμ΄λ³΄μ
- κ²°κ³Ό : μ νμ± 75μ (15/15), ν¨μ¨μ± 15μ (3/5), μ΄ 90μ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int solution(vector<int> people, int limit)
{
int answer = 0;
sort(people.begin(), people.end());
while (people.size() > 0)
{
int i = people.size() - 1;
if ((i != 0) && (people[0] + people[i] <= limit))
{
answer++;
people.erase(people.begin() + i);
if (people.size() >= 1)
people.erase(people.begin());
}
else
{
answer++;
people.erase(people.begin() + i);
}
}
return answer;
}
μ²μμλ λ¨μν Vector μμ Lightest
μ Heaviest
μμλ₯Ό erase ν¨μλ₯Ό ν΅ν΄ μ§μλκ°λ©΄μ νμ΄λκ°λλ°,
μ΄ λ°©λ²μ μ νμ± ν
μ€νΈλ λͺ¨λ ν΅κ³Όνμ§λ§, ν¨μ¨μ± ν
μ€νΈμμ 1λ² 3λ² μκ° μ νμ ν΅κ³Όνμ§ λͺ»νλ€.
κ·Έ μ΄μ λ λ©μΈ 루νμμ Lightest
λ₯Ό μ κ±°ν΄λκ° λ μ€λ²ν€λκ° λ°μν΄μμΈκ² κ°λ€.
Vector μμ νΉμ μμλ‘€ erase λ‘ μ κ±°νλ©΄ ν΄λΉ μμμ 곡κ°μ λΉ κ³΅κ°μ΄ λλλ°,
Vectorλ μμ°¨ μλ£κ΅¬μ‘°μ΄κΈ° λλ¬Έμ, μ κ±°ν μμ λ€μ λͺ¨λ μμλ€μ ν μΉΈμ© μμΌλ‘ λ‘겨 μ¬ν λΉν΄μ€λ€.
λ΄ νμ΄μμλ Vector 맨 μμμ μ‘΄μ¬νλ Lightest
λ₯Ό μ κ±°νλ κ²½μ°κ° λΉμΌλΉμ¬νκΈ°μ,
μ΄ κ³Όμ μμ μ€λ²ν€λκ° λ§μ΄ λ°μνμ κ²μΌλ‘ μΆμΈ‘λλ€.
λ¬Έμ 쑰건μ μν΄ λ¬΄μΈλμ κ°ν μ¬λμ μ΅λ 50000λͺ μ΄λ―λ‘, μ΅μ μ κ²½μ°, μμλ€μ ν μΉΈμ© λΉκΈ°λ κ³Όμ μ 49998λ², 49996λ², 49994λ², β¦ μ§ννκ² λλ€.
π λ λ²μ§Έ νμ΄
- μ½λ μλ : μλ.. μλ.. μλ..!
- κ²°κ³Ό : μ νμ± 75μ (15/15), ν¨μ¨μ± 15μ (5/5), μ΄ 100μ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
int solution(vector<int> people, int limit)
{
int necessaryLifeBoatCount = 0;
int count[241] = { };
// Record Every Weight
int first = 40;
int end = 240;
// First Will Be The Lightest Weight
// End Will Be the Heaviest Weight
for (int i = 0; i < people.size(); i++)
count[people[i]]++;
while (true)
{
if (first == end)
{
break;
}
if (count[first] == 0)
{
first++;
continue;
}
if (count[end] == 0)
{
end--;
continue;
}
// If The Sum Of Lightest Weight And Heaviest Weight Is Smaller Or Equals To The Limit
// Ride Them A Boat
if (first + end <= limit)
{
int temp = min(count[first], count[end]);
count[first] -= temp;
count[end] -= temp;
necessaryLifeBoatCount += temp;
}
// If Not, The Heaviest People Can Only Ride A Boat By Themselves,
// So Each Person With That Weight Picks Up One Boat
else
{
necessaryLifeBoatCount += count[end];
count[end] = 0;
}
}
if (count[first] > 0)
{
if ((count[first] > 1) && (first + first <= limit))
{
necessaryLifeBoatCount += count[first] / 2;
necessaryLifeBoatCount += count[first] % 2;
}
else
{
necessaryLifeBoatCount += count[first];
}
}
return necessaryLifeBoatCount;
}
λ λ²μ§Έ νμ΄μμλ μλλ₯Ό μ΅λν λνλ³΄κ³ μ νλ€.
μ€μ λ‘ μ΄ νμ΄λ λ΄ νμ΄ μ€ κ°μ₯ λΉ λ₯Έ νμ΄μ΄κΈ°λ νλ€.
μ΄ νμ΄μμλ λ§μΉ μΉ΄μ΄ν
μ λ ¬μ²λΌ,
Count
λ°°μ΄μ λ§λ€κ³ , κ±°κΈ°μ κ° μΈλ±μ€λ₯Ό 무κ²
λ‘ νλ μ¬λ μλ₯Ό μ μ₯νλ€.
μλ₯Ό λ€μ΄ Input μΌλ‘ λ€μ΄μ¨ People μ΄ [ 40, 50, 80, 40, 90 ] μ΄λΌλ©΄,
Count
[40] μ 40KG μΈ μ¬λμ μμΈ 2
μ΄λ€.
μ΄λ° Count
λ°°μ΄μ λ§λ€μ΄μ€ μ΄μ λ λ κ°μ§κ° μλ€.
μ μ λ μ¬λμ 무κ²κ° 40KG ~ 240KGμΌλ‘ λΉκ΅μ μ’μ λ²μλ‘ νμ λμ΄ μλλ°, μ¬λμ μλ 1λͺ
~ 50,000λͺ
μ΄λ λλ€λ κ².
- λλ¬Έμ κ°μ λͺΈλ¬΄κ²λ₯Ό κ°μ§ μ¬λμ΄ λ§μ κ²μ΄κ³ , μ΄λ‘ μΈν΄ μ€λ³΅λλ μ²λ¦¬κ° λ§μ κ²μ΄λΌκ³ μκ°νλ€. μ΄λ° μ€λ³΅λ μ²λ¦¬λ€μ
Count
λ°°μ΄μ μ΄μ©ν΄ ν λ²μ μ²λ¦¬νκ³ μ νλ€. - 그리κ³
그리λ
μ΄κΈ° λλ¬Έμ λͺ¨λ μμμ μ κ·Όμ ν΄μΌνλλ°, Vectorλ₯Ό μΈλ±μ€λ‘ μ κ·Όνλ κ²λ³΄λ€, λ°°μ΄μ μΈλ±μ€λ‘ μ κ·Όνλ κ²μ΄ μλκ° ν¨μ¬ λΉ¨λλ€.
μ¬κΈ°μ λ κ°μ ν¬μΈν° (μ£Όμλ₯Ό κ°λ¦¬ν€λ ν¬μΈν°κ° μλλΌ λ§ κ·Έλλ‘ ν¬μΈν°) λ₯Ό λ§λ€μλ€.
Lightest
: νμ¬ λ¬΄μΈλμ λ¨μμλ μ¬λλ€ μ€ κ°μ₯ κ°λ²Όμ΄ μ¬λμ 무κ²
Heaviest
: νμ¬ λ¬΄μΈλμ λ¨μμλ μ¬λλ€ μ€ κ°μ₯ λ¬΄κ±°μ΄ μ¬λμ 무κ²
Count
λ°°μ΄μμμ μΈλ±μ€λ μ¬λμ 무κ²μ λμλλ―λ‘,
Count[Lightest]
λ κ°μ₯ κ°λ²Όμ΄ 무κ²μ μ¬λ μ, Count[Heaviest]
λ κ°μ₯ λ¬΄κ±°μ΄ λ¬΄κ²μ μ¬λ μλ₯Ό μλ―Ένλ€.
μ΄λ₯Ό μ΄μ©ν΄ λ©μΈ 루νλ 맀 λ°λ³΅ λ§λ€, μλ λ κ°μ§ μμ μ€ ν μμ μ μ€ννλ€.
Lightest
μHeaviest
λ λͺ μ 보νΈμ νμ ꡬμΆνλ€.Heaviest
ν λͺ λ§ λ³΄νΈμ νμ ꡬμΆνλ€.
Lightest
μ Heaviest
μ λ¬΄κ² ν©μ΄ ꡬλͺ
λ³΄νΈ λ¬΄κ² μ νμ λμ§ μμΌλ©΄,
Lightest
μ Heaviest
λ λͺ
μ 보νΈμ νμ보λ΄κ³ ,
Lightest
μ Heaviest
μ λ¬΄κ² ν©μ΄ ꡬλͺ
λ³΄νΈ λ¬΄κ² μ νμ λμ§ μμΌλ©΄,
Heaviest
λ νΌμμ λ°μ 보νΈλ₯Ό ν μ μμΌλ―λ‘ νΌμ 보νΈμ νμ ꡬμΆνλ€.
(κ°μ₯ κ°λ²Όμ΄ Lightest
λ μ§μ μ§μμμλ λ¬΄κ² μ νμ λμΌλ―λ‘)
π μ΅μ’ νμ΄
- μ½λ μλ : μλ.. κ·Έλ¦¬κ³ κ°λ μ±
- κ²°κ³Ό : μ νμ± 75μ (15/15), ν¨μ¨μ± 15μ (5/5), μ΄ 100μ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit)
{
int boatCount = 0;
int lightest = 0;
int heaviest = people.size() - 1;
sort(people.begin(), people.end());
while (lightest <= heaviest)
{
if (people[lightest] + people[heaviest] <= limit)
lightest++;
heaviest--;
boatCount++;
}
return boatCount;
}
μ½ν
μ€ν°λ λͺ¨μμμ νμλ₯Ό ν΄λ³΄λ,
λ€λ₯Έ λ νμ λΆλ€μ λͺ¨λ μ΄λ°μμΌλ‘ νΈμ
¨μλ€.
κΈ°λ³Έμ μΈ μκ³ λ¦¬μ¦ μ체λ κΈ°μ‘΄κ³Ό λΉμ·νκ³ , ꡬνμ 첫 λ²μ§Έ νμ΄μ λ λ²μ§Έ νμ΄λ₯Ό μμ κ²μ²λΌ λ¬λΌμ‘λ€.
μ΄ νμ΄λ 첫 λ²μ§Έ νμ΄μ²λΌ Vectorλ₯Ό μ΄μ©νλ, μ΄λ²μλ μμλ₯Ό μ§μ°μ§λ μκ³ ,
λ λ²μ§Έ νμ΄μ²λΌ Lightest
μ Heaviest
λ κ°μ ν¬μΈν°λ₯Ό μ΄μ©ν΄ νμ¬ κ³Όμ μμ μ²λ¦¬ν μμλ₯Ό κ²°μ νλ€.
μλλ λ λ²μ§Έ νμ΄κ° ν¨μ¬ λ λΉ λ₯΄κΈ΄ νμ§λ§, (μ νμ± ν
μ€νΈμμ, μ½ .01ms VS μ½ .03ms)
μ΄ νμ΄μ κ°λ
μ±μ΄ μ λ³΄λ€ ν¨μ¬ μ’λ€κ³ μκ°νκΈ°μ μ΄λ₯Ό μ΅μ’
νμ΄λ‘ κ²°μ νλ€.