오늘의 문제는 어렵지 않았다. 하지만 어째서인지 런타임에러, 참조할 수 없는 범위 라는 오류가 자꾸 떴다.. 알 수 없었다..오늘도 틀린 코드와 맞은 코드 둘 다 가져왔다.
틀린 코드 1 (런타임에러)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int k , n;
string a;
vector<int>v;
int main() {
cin >> n >>k;
cin >> a;
for (int i = 0; i < n; i++) {
v.push_back(a[i]-'0');
}
sort(v.begin(), v.end());
cout << v[k];
}
틀린 코드 2 (시간 초과)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int k , n ,a;
vector<int>v;
int main() {
cin >> n >>k;
k = k - 1;
for (int i = 0; i < n; i++) {
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
cout << v[k];
}
1번 코드는 a[i] - '0' 이걸 쓰려면 숫자가 한자리수인 것만 적용이 가능하다.
또 입력을 받을 때 공백도 같이 받기 때문에 cin을 사용할 수 없다. 그래서 getline으로 받아보려고 했다. 하지만 그렇게 되면 index계산을 어떻게 하지? 라는 생각에 그만두었다.
2번 코드는 시간 초과로 오류가 났는데 cin , cout을 쓸 때는 "cin.sync_with_stdio(0); cin.tie(0);" 을 써줘야 한다.
맞은 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int k , n ,a;
vector<int>v;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >>k;
k = k - 1;
for (int i = 0; i < n; i++) {
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
cout << v[k];
}
처음에는 k 값은 그대로 받기만하고 넣으면 된다고 생각했다. out of range 가 난 이유가 바로 이것인 것 같다.숫자는 5개 받지만 k를 5를 받게 되면 v[5]를 참조하게 되는데 이는 없는 값이다.
c++에서의 sort는 병합정렬이다.
이 문제의 시간 제한은 2초이다. 그럼 최대 2억번을 연산한다는 이야기이다.
문제에서 n은 5백만까지 가능했는데 만약 시간 복잡도가 n제곱인 연산을 하게되면 2억번을 넘게된다.
따라서 이 문제에서 버블정렬과 선택정렬 시간 복잡도가 n제곱인 정렬을 사용했다면 시간 초과가 났을 것이다.
엄청 빨리 풀 수 있을거라고 자신했는데 그렇지 못했다.. 아쉽지만 오늘의 문제는 쉬워서 그런건지는 몰라도 주변사람한테 의존하지 않고 혼자서 해결하려고 했던 것 같아 뿌듯하다. 이런 문제만 풀고싶다... 시간 복잡도는 교수님 연구실에서 공부할 때 열심해 배웠던 건데.. 기억이 잘 안 난다...(최악..) 다음 주부터는 교육을 들어서 자바 공부가 더 시급하다.. 내일부터는 자바도 공부해야겠다. 화이팅
