오늘은 map이라는 라이브러리를 공부해보았다. map<type ,type>변수이름 이런 형태이다. map은 key와 value가 짝을 지어 저장된다. map은 트리(균형을 이룸) 구조 형태이기 때문에 데이터를 찾고 삽입하고 삭제하는 시간 복잡도는 O(log n)시간이 든다. 또한 map은 key값이 들어갈 때 정렬되어서 들어가기 때문에 따로 정렬할 필요가 없다.
오늘도 틀린 코드 두 개와 맞은 코드를 한 개 들고 왔다. 틀린 코드는 하나는 map을 이용해서 다른 하나는 배열을 이용했는데 둘 다 시간초과가 났다..
#include<iostream>
using namespace std;
int k , n , l ;
string a[10001];
string b;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n>>k ;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int j = 0; j < k; j++) {
cin >> b;
for (int m = 0; m < n; m++) {
if (a[m] == b) {
l++;
}
else continue;
}
}
cout << l;
}
이 코드에서 시간 초과가 난 이유
2중 for문 안에서 k와 n의 최대 값이 각 각 10000이다. 따라서 1억번 연산하게된다. b의 최대의 길이는 499인데 문자열비교를 해버리면 499억의 시간이 걸리게된다. 문제의 제한 시간읜 2초 즉 2억번 연산하는 것인데 그를 훨씬 넘어 시간 초과가 뜨게된 것이다.
밑의 경우도 같은 이유같다.
틀린 코드 2
#include<iostream>
#include<map>
using namespace std;
int k , n , l ;
string a ,b ;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n>>k ;
map<int, string>ma;
for (int i = 0; i < n; i++) {
cin >> a;
ma.insert(make_pair(i , a));
}
for (int j = 0; j < k; j++) {
cin >> b;
for (auto it = ma.begin(); it != ma.end(); it++) {
if (it->second == b) {
l++;
}
else continue;
}
}
cout << l;
}
맞은 코드
#include<iostream>
#include<map>
using namespace std;
int k , n , l ;
string b;
map<string, int>ma;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n>>k ;
for (int i = 0; i < n; i++) {
cin >> b;
ma.insert(make_pair(b ,i));
}
for (int j = 0; j < k; j++) {
cin >> b;
if (ma.count(b)) l++;
else continue;
}
cout << l;
}
코드를 좀 더 간단하게 만들 수 있다.
ma.insert({b,i}) 로 바꿀 수 있다. 그리고 insert 를 쓰지 않고 ma[b] ++; 이렇게 하면 ma.count(b)를 쓰지 않고 이 문제를 풀 수 있다.
ma[b]++ 는 b라는 key값에 value에 1이 들어간 것이다.
위와 같이 쓰게 되면 ma.count(b) 를 if(ma[b] == 1) l++; 로 고칠 수 있다.
오늘도 그렇게 어렵지는 않았는데 시간 초과문제가 정말 거슬렸다. 시간 복잡도가 정말 중요한 것 같다. 오늘 처음으로 JAVA공부해봤는데 main을 선언하는 것부터가 너무 별로다.. 최악.. 화이팅
