링크 : https://www.acmicpc.net/problem/1822
복습할 게 많은 문제다.
이렇게 하니까 시간 초과가 걸린다. .size() 이런 것도 다 변수로 정리했음에도 불구하고 계속 시간 초과가 나왔다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> dif(vector<int>& a, vector<int>& b);
int main() {
int a_n, b_n;
cin >> a_n >> b_n;
vector<int> a, b, answer;
int elem;
for (int i = 0; i < a_n; i++) {
cin >> elem;
a.push_back(elem);
}
for (int i = 0; i < b_n; i++) {
cin >> elem;
b.push_back(elem);
}
answer = dif(a, b);
if (answer.size() == 0) {
cout << "0";
return 0;
}
else {
cout << answer.size() << endl;
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << "\t";
}
return 0;
}
}
vector<int> dif(vector<int>& a, vector<int>& b) {
vector<int> c;
for (int i = 0; i < a.size(); i++) {
bool exist = false;
for (int j = 0; j < b.size(); j++) {
if (a[i] == b[j])
exist = true;
}
if (!exist)
c.push_back(a[i]);
}
return c;
}그래서 검색해 봤는데 set library를 이용하여 문제를 풀 수 있었다.
set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 노드 기반 컨테이너로 빠른 접근이 가능했다. 특히 for문으로 돌릴 때 인덱스로 접근하는 것이 아니라 iterator로 접근 할 수 있었다. set이 vector와 상당히 비슷해서 사용하기엔 문제 없었다. 다만 set은 <int>의 형식만을 갖는다.
참고 : https://hyeonstorage.tistory.com/327
#include <iostream>
#include <set>
using namespace std;
int main() {
int a_n, b_n, elem;
cin >> a_n >> b_n;
set<int> a;
bool exist = false;
for (int i = 0; i < a_n; i++) {
cin >> elem;
a.insert(elem);
}
for (int i = 0; i < b_n; i++) {
cin >> elem;
auto it = a.find(elem);
if (it == a.end())
continue;
else
a.erase(it);
}
cout << a.size() << endl;
if (a.size() != 0) {
for (auto elem : a)
cout << elem << " ";
}cout << endl;
return 0;
}
b 컨테이너를 따로 저장하지 않았다. b를 받으면서 a에 저장되어있는 요소 중에 존재하면 a를 지우는 형태로 진행했다.
auto it = a.find(elem);iterator 설정할 때 헷갈리면 auto로 설정하기.
for (auto elem : a)
cout << elem << " ";간만에 for문 저렇게 꺼내는 것 복습하기.
그럼 이를 응용해서 벡터로 접근한다면?
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int a_n, b_n;
cin >> a_n >> b_n;
vector<int> a;
int elem;
for (int i = 0; i < a_n; i++) {
cin >> elem;
a.push_back(elem);
}
for (int i = 0; i < b_n; i++) {
cin >> elem;
auto here = find(a.begin(), a.end(), elem);
if (here != a.end())
a.erase(here);
}
cout << a.size() << endl;
if (a.size() != 0) {
for (auto elem : a) {
cout << elem << " ";
}
return 0;
}
}그래도 시간 초과가 걸린다.
왜 시간 초과에 계속 걸리나 짜증나서 검색해봤는데 다음과 같이 이유를 찾을 수 있었다.
벡터가 연산에 시간이 오래 걸린다. 따라서 최대 입력 개수를 알 때에 reserve하거나 아니면 배열로 쓰거나.
그리고 출력값 내놓을 때 "\t"가 아니라 " "로 해야 한다. 안그러면 출력 형식 오류 뜬다.. 후.. 이런건 알아서 처리하면 안되나.. 하지만 시키는 대로 해야하니 다음부터는 이런거로 실수하지 말자..
