Baekjoon(C++)
[C++]백준 알고리즘 1269번
DanielSoliph
2021. 6. 27. 14:34
풀이는 아래와 같다.
|
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
|
#include <iostream>
#include <map>
using namespace std;
int main(){
int a,b;
map<int,int> m;
scanf("%d %d",&a,&b);
int* first = new int[a];
int* second = new int[b];
for(int i=0;i<a;i++){
scanf("%d",&first[i]);
m[first[i]]++;
}
int n = 0;
for(int j=0;j<b;j++){
scanf("%d",&second[j]);
if(m[second[j]]){
n++;
}
}
// bool skip = false;
// for(int i=0;i<a;i++)
// {
// skip = false;
// for(int j=0;j<b;j++)
// {
// if(first[i] == second[j])
// {
// n++;
// skip = true;
// break;
// }
// }
// if(skip == true){
// continue;
// }
// }
printf("%d\n",a+b-2*n);
delete[] first;
delete[] second;
}
|
cs |
시행착오:
처음에 이 문제를 풀 때는 아래의 주석 처리된 코드와 같이 무식하게 했었는데, 시간초과로 에러가 났다.
a와 b에서 교집합을 확인하는데 걸리는 시간이 O(n^2)라서 입력이 많을 경우에 굉장히 시간이 오래 걸리는 것 같다.
다른 블로그의 글을 참고해 map 라이브러리를 사용하여 문제를 해결해보았다. 아직 많이 모자라지만 더 열심히 해보자... 뭔가 끝까지 혼자서 해내고 싶었지만 시간초과가 자꾸 나서 답답했다. ㅋㅋㅋㅋㅋ 휴 너무 초보다 나,,, 학교 수업 과제나 할줄 알았지 알고리즘과 코드의 효율성에 대해서는 거의 모르는 것 같다. 앞으로 문제를 풀 때마다 짧게나마 이런 기록을 남기려고 한다.
+ 찾아보니 map의 경우 포인터가 value인 경우 NULL로 초기화, 일반 변수인 경우 0으로 초기화된다고 한다.
추가정보:
처음으로 오늘 코드를 ColorScripter를 사용해서 업로드해보았다. 이쁘고 좋은 거 같다. 앞으로도 애용해보자
반응형