1931 풀기
아는 사람이 백준 문제를 풀고있는데 런타임 에러가 난다면서 코드를 한번 봐달라고 했다.
초기코드
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct beginend {
unsigned int begin;
unsigned int end;
};
vector<beginend> a;
bool comp(beginend x, beginend y) {
return x.end <= y.end;
}
int main() {
int n, count = 0;
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].begin >> a[i].end;
}
sort(a.begin(), a.end(), comp);
unsigned int time = 0;
for (int i = 0; i < n; i++) {
if (a[i].begin >= time) {
time = a[i].end;
count++;
}
}
cout << count << endl;
return 0;
}
자려고 누웠는지라 코드만보고 대충 이거아님? 저거아님? 하면서 개소리만 하다가
결국 못 버티고 일어나서 컴퓨터 켜서 돌렸다.
그러고나서 깨달은게
1
2
3
bool comp(beginend x, beginend y) {
return x.end <= y.end;
}
이거 같은값 들어갔을때 sort에서 무한루프 돌아서 런타임에러나는거 아닌가? 란 생각이 들어서.
등호를 때고 제출했다.
틀렸습니다.
이것저것 테스트해보면서 예제 테스트케이스를 뒤집어 넣어보고 이것저것 해보니까 깨달은게있다.
뒷순서로만 정렬을 할때 앞값이 큰값이 앞에 놓이는 경우도 있겠네
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct beginend {
unsigned int begin;
unsigned int end;
};
vector<beginend> a;
bool comp(beginend x, beginend y) {
return x.end < y.end;
}
bool comp2(beginend x, beginend y) {
return x.begin < y.begin;
}
int main() {
int n, count = 0;
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].begin >> a[i].end;
}
sort(a.begin(), a.end(), comp2);
stable_sort(a.begin(), a.end(), comp);
/*for (auto i : a)
{
cout << i.begin << ' ' << i.end << endl;
}*/
unsigned int time = 0;
for (int i = 0; i < n; i++) {
if (a[i].begin >= time) {
time = a[i].end;
count++;
}
}
cout << count ;
return 0;
}
제일 먼저 생각난 방법은 시작값을 기준으로 먼저 정렬하고 stable_sort로 뒷값을 정렬해주는 방법이었다.
sorting을 두번이나하는 비효율적이지만 잠이 왔기에 더이상 생각하기 싫었고 코드는 간단했다.
92.ms로 통과하고 잤다.
성능충인 나는 자고 일어나서 비효율적인코드를 고칠생각을 했다.
첫번째로 cin, cout 개선
1
2
3
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
그다음에 sort한번에 모든게 정렬되도록 comp를 손봤다.
comp를 고치고 sort를 고쳤을땐 92 ->88
- io 개선 -> 24ms
전체코드 24ms
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct beginend {
unsigned int begin;
unsigned int end;
};
vector<beginend> a;
bool comp(const beginend &x,const beginend& y) {
if (x.end !=y.end)
{
return x.end < y.end;
}
else
{
return x.begin < y.begin;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, count = 0;
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].begin >> a[i].end;
}
sort(a.begin(), a.end(), comp);
//stable_sort(a.begin(), a.end(), comp);
/*for (auto i : a)
{
cout << i.begin << ' ' << i.end << endl;
}*/
unsigned int time = 0;
for (int i = 0; i < n; i++) {
if (a[i].begin >= time) {
time = a[i].end;
count++;
}
}
cout << count ;
return 0;
}
CLRS greedy 첫번째 예제로 쓰일만큼 유명한 활동선택 문제이다. 알고리즘 공부에 필수적으로 풀어야할 문제
Posted 2020-01-29