📝10816번: 숫자카드2
문제 설명
숫자카드2
해결 방법
N개의 입력들을 v1 벡터에 넣고, M개의 입력들을 v2 벡터에 넣는다.
v1 벡터를 오름차순 정렬하고, 이진탐색을 기반으로 시간복잡도가 O(log n)인 lower_bound와 upper_bound 함수를 활용한다.
lower_bound의 경우 인자로 들어오는 값 이상인 첫번째 원소의 반복자를 반환하고, upper_bound의 경우 인자로 들어오는 값을 초과하는 첫번째 원소의 반복자를 반환하므로 각각의 인덱스를 구해서 빼주면 그 숫자의 개수가 나온다.
💻소스코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, num1, M, num2;
vector<int> v1, v2;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> num1;
v1.push_back(num1);
}
cin >> M;
for (int i = 0; i < M; i++) {
cin >> num2;
v2.push_back(num2);
} // 입력
sort(v1.begin(), v1.end());
for (int i = 0; i < M; i++) {
auto lb = lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
auto ub = upper_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
cout << ub - lb << " ";
} // 출력
return 0;
}📝1764번: 듣보잡
문제 설명
듣보잡
해결 방법
듣도 못한 사람과 보도 못한 사람이 중복되는 수와 이름을 출력해야한다. 입력을 받아서 전부 v 벡터에 넣고 오름차순 정렬한다. 오름차순 정렬하게 되면 중복되는 string의 경우 연속된 위치에 있게 된다. 반복문을 실행해서 연속된 위치에 있는 동일한 string을 count하고 새로운 same 벡터에 넣는다.
마지막으로 cnt와 same 벡터를 출력한다.
💻소스코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
int cnt = 0;
string name;
vector<string> v, same;
cin >> N >> M;
for (int i = 0; i < N + M; i++) {
cin >> name;
v.push_back(name);
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size() - 1; i++) {
if (v[i] == v[i + 1]) {
cnt++;
same.push_back(v[i]);
}
}
cout << cnt << "\n";
for (auto i : same)
cout << i << "\n";
return 0;
}📝1269번: 대칭 차집합
문제 설명
대칭 차집합
해결 방법
대칭 차집합의 원소 개수를 구하는게 결국 두 집합의 교집합을 제외한 원소의 개수이다.
1. 집합 A의 원소 개수와 집합 B의 원소 개수를 더해서 cnt에 저장한다.
2. 집합 A의 원소와 집합 B의 원소들을 입력받아 s_A, s_B set에 각각 insert한다.
3. find 내장함수를 사용한다. 집합 A(혹은 B)의 원소가 집합 B에 있다면(혹은 A에 있다면) 교집합의 원소이므로 cnt에서 2개를 뺀다. (1. 에서 중복으로 원소의 개수를 더했기 때문이다.)
4. cnt 출력
💻소스코드
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int A, B, num; // 집합 A의 원소의 개수, 집합 B의 원소의 개수, 숫자 입력
set<int> s_A, s_B; // 집합 A, 집합 B
cin >> A >> B;
int cnt = A + B;
for (int i = 0; i < A; i++) {
cin >> num;
s_A.insert(num);
}
for (int i = 0; i < B; i++) {
cin >> num;
s_B.insert(num);
}
for (auto a : s_A) {
if (s_B.find(a) != s_B.end())
cnt -= 2;
}
cout << cnt << "\n";
return 0;
}📝11478번: 서로 다른 부분 문자열의 개수
문제 설명
서로 다른 부분 문자열의 개수
해결 방법
substr을 사용하여 문자열 S의 부분문자열을 추출하고 set에 insert한다.
set을 사용하면 중복되는 원소가 없으므로 서로 다른 부분 문자열들을 구할 수 있다.
while문으로 문자열의 진부분집합을 구했으므로 출력할 때 set의 size에 1을 더해서 출력한다.
좀 까다롭게 푼 것 같아서 다른 사람의 풀이를 봤다. 원리는 같지만 간결했다.
- 나의 풀이
💻소스코드
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string S;
set<string> s_each_subs;
cin >> S;
int len = S.size();
int idx = 0, npos = 1;
while (true) {
if (idx + npos > len || idx == len) {
npos++;
idx = 0;
}
string subs = S.substr(idx, npos);
if (subs != S)
s_each_subs.insert(subs);
else
break;
idx++;
}
// s_each_subs.size()는 진부분집합의 개수이므로 부분집합의 개수는 1을 더해야함.
cout << s_each_subs.size() + 1 << "\n";
return 0;
}- 다른 사람들의 풀이
💻소스코드
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
string S;
cin >> S;
set<string> set;
string str = "";
for (int i = 0; i < S.size(); i++) {
for (int j = i; j < S.size(); j++) {
str += s[j];
set.insert(str);
}
str = "";
}
cout << set.size();
}
