백준 BOJ 6325번 : Definite Values
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
N개의 (변수) = (변수) 꼴의 수식이 주어지고, 처음에는 a만 값이 제대로 지정되었다고 할 때, 모든 등식이 적용된 이후 값이 제대로 지정된 변수의 목록을 구하는 문제이다.
set을 사용한다.
a = b라는 등식에서, a가 값이 지정되지 않고 b가 지정되었다면 a는 제대로 된 값이 지정된다. (set에 insert 해준다.)
반대로 a가 값이 지정되고 b가 지정되지 않았다면 a의 값은 쓰레기 값으로 덮어진다. (set에서 erase 해준다.)
이 과정을 N번 반복한 다음 set의 모든 원소들을 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int t=1; ; t++) {
int N; cin >> N;
if(N == 0) break;
set<string> s;
s.insert("a");
while(N--) {
string a, op, b; cin >> a >> op >> b;
if(s.count(a) == 0 && s.count(b) > 0) s.insert(a);
else if(s.count(a) > 0 && s.count(b) == 0) s.erase(a);
}
cout << "Program #" << t << "\n";
if(s.size() > 0) {
for(auto i : s) cout << i << " ";
}
else cout << "none";
cout << "\n\n";
}
}
백준 BOJ 8975번 : PJESMA
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
N개의 단어가 주어지고, M개의 단어가 주어질 때 이 M개의 단어들을 순서대로 보면서 N개의 단어 중에 있으면 체크한다면 N개의 단어 중 절반 이상이 체크될 때 M개의 단어들 중 몇 번째 단어까지 체크해야 하는지 구하는 문제이다.
먼저 N개의 단어는 set에 저장해주고, M개의 단어들을 순서대로 확인하면서 count 해주면 된다.
다만 M개의 단어들 중에서 중복이 있기 때문에 map을 이용하여 중복이 발생하지 않도록 해주자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
set<string> s;
for(int i=0; i<N; i++) {
string str; cin >> str;
s.insert(str);
}
int M; cin >> M;
vector<string> v(M);
for(int i=0; i<M; i++) cin >> v[i];
unordered_map<string, bool> m;
int cnt = 0;
for(int i=0; i<M; i++) {
if(m[v[i]]) continue;
m[v[i]] = true;
if(s.count(v[i]) > 0) cnt++;
if(cnt >= (N+1)/2) {
cout << i+1 << "\n";
break;
}
}
}
백준 BOJ 4775번 : Spelling Be
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
사전에 있는 단어들이 주어지고, 각 이메일에 대해 사전에 없는 단어들이 있으면 그 단어들을 출력하는 문제이다.
Set을 사용하여 쉽게 풀이할 수 있다.
사전에 있는 단어들을 Set에 넣어주고, 각 이메일들에 대해 Set에 단어가 있는지 체크하여 없으면 벡터에 저장해준 뒤 마지막에 모두 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
multiset<string> s;
while(N--) {
string str; cin >> str;
s.insert(str);
}
int T; cin >> T;
for(int t=1; t<=T; t++) {
vector<string> v;
while(true) {
string str; cin >> str;
if(str == "-1") break;
if(s.count(str) == 0) v.push_back(str);
}
if(v.size() == 0) {
cout << "Email " << t << " is spelled correctly.\n";
}
else {
cout << "Email " << t << " is not spelled correctly.\n";
for(int i=0; i<v.size(); i++) cout << v[i] << "\n";
}
}
cout << "End of Output\n";
}
백준 BOJ 5390번 : Gene Shuffle
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
N 이하의 자연수로 이루어진 두 개의 순열에 대해, 부분 원소가 같은 부분 집합을 최대한 많이 쪼개지도록 찾는 문제이다.
set을 사용하여 원소를 순서대로 2개의 set에 넣어주다가 두 set이 같아질 때 그 구간을 출력해주면 된다.
여담으로 unordered_set을 사용해봤는데 시간 초과가 발생했다.
set의 경우 탐색 시간이 O(log N)인 것에 비해 unordered_set은 O(1)일 때도 있고 최악의 경우 O(N)이라고 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
int cur = 0;
while(cur < N) {
set<int> sv, su;
for(int i=cur; i<N; i++) {
sv.insert(v[i]);
su.insert(u[i]);
if(sv == su) {
cout << cur+1 << "-" << i+1 << " ";
cur = i+1;
break;
}
}
}
cout << "\n";
}
}
백준 BOJ 15081번 : Is Everbody Appy?
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
N명의 사람들이 원하는 앱의 이름들이 주어지고 (먼저 나오는 이름이 우선순위가 높은 앱), 각 사람은 한 개의 앱만을 받을 수 있으며, 먼저 나오는 사람이 우선 순위일 때 각 사람이 받아야 하는 앱의 이름을 구하는 문제이다.
맨 윗 사람부터 그리디하게 앞의 앱부터 set을 체크해보면서 set에 없는 이름일 경우 그 앱을 출력해주고 set에 추가해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
set<string> s;
while(N--) {
int M; cin >> M;
vector<string> v(M);
for(int i=0; i<M; i++) cin >> v[i];
for(int i=0; i<M; i++) {
if(s.count(v[i]) == 0) {
cout << v[i] << " ";
s.insert(v[i]);
break;
}
}
}
cout << "\n";
}
백준 BOJ 17048번 : Jarvis
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
배열 A와 B가 주어질 때, A의 전체에 x를 더하여 B와 일치하는 원소 수가 최대가 되게 하려고 할 때, 최대로 일치하는 원소 수를 구하는 문제이다.
map을 사용하여 격차(b[i] - a[i])들을 모두 저장해주고, 그들 중 빈도가 가장 높은 격차의 횟수를 답으로 얻어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
map<int, int> m;
vector<int> w;
for(int i=0; i<N; i++) {
if(m[u[i] - v[i]] == 0)
w.push_back(u[i] - v[i]);
m[u[i] - v[i]]++;
}
int ans = 0;
for(int i=0; i<w.size(); i++) ans = max(ans, m[w[i]]);
cout << ans << "\n";
}
백준 BOJ 18703번 : Duplicate Files
문제 난이도 : Silver V
알고리즘 분류: 트리를 사용한 집합과 맵
여러 파일들의 이름과 번호가 주어질 때, 동일한 이름의 파일은 번호가 더 낮은 것만을 남긴다고 한다면 마지막으로 남는 파일들의 번호들을 구하는 문제이다.
map을 사용하여 번호를 저장하고, 만약 번호가 없을 경우 추가해주고 번호가 있는데 새로 입력된 파일의 번호가 더 작을 경우 갱신해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
unordered_map<string, int> m;
vector<string> v;
while(N--) {
string str; cin >> str;
int x; cin >> x;
if(m[str] == 0) {
m[str] = x;
v.push_back(str);
}
else m[str] = min(m[str], x);
}
vector<int> u;
for(int i=0; i<v.size(); i++) u.push_back(m[v[i]]);
sort(u.begin(), u.end());
for(int i=0; i<u.size(); i++) cout << u[i] << " ";
cout << "\n";
}
}
백준 BOJ 18706번 : Coffee
문제 난이도 : Silver V
알고리즘 분류 : 트리를 사용한 집합과 맵
N개의 커피의 종류와 가격(small, medium, large의 가격), M명의 이름과 원하는 커피가 주어지며, 배송료 100달러를 M명이 나눠서 지불할 때 최종적으로 각 사람이 내야 하는 가격을 구하는 문제이다.
(이 때 5의 배수 ±1인 경우는 가까운 5의 배수로 반올림해야 한다.)
map을 사용하여 문제에서 주어진 조건대로 구현하면 되는 구현 문제이다.
배송료는 100 / M을 더해서 구해줄 수 있으며, 최종적으로 이 가격에 5로 나눈 나머지가 1 또는 4일 때만 추가적인 처리를 해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N, M; cin >> N >> M;
map<string, int> ms, mm, ml;
for(int i=0; i<N; i++) {
string str; cin >> str;
int a, b, c; cin >> a >> b >> c;
ms[str] = a;
mm[str] = b;
ml[str] = c;
}
for(int i=0; i<M; i++) {
string a, b, c; cin >> a >> b >> c;
int ans = 0;
if(b == "small") ans += ms[c];
else if(b == "medium") ans += mm[c];
else if(b == "large") ans += ml[c];
ans += 100 / M;
if(ans % 5 == 1) ans--;
else if(ans % 5 == 4) ans++;
cout << a << " " << ans << "\n";
}
}
}
백준 BOJ 7847번 : Sales Report
문제 난이도 : Silver IV
알고리즘 분류 : 트리를 사용한 집합과 맵
각 물건에 대해 2개의 고유한 id가 주어지고, 이들의 판매 수량이 주어질 때 2차원 표를 만들어 각 id에 해당하는 물건의 수의 합을 구하는 문제이다.
map을 pair<int, int> → int로 선언하여, 각 id 쌍에 대한 map의 값을 갱신해준 뒤, 문제에서 만들라고 하는 대로 표를 출력해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v, u;
map<pair<int, int>, int> m;
while(N--) {
int a, b, c; cin >> a >> b >> c;
v.push_back(a);
u.push_back(b);
m[{a, b}] += c;
}
sort(v.begin(), v.end());
sort(u.begin(), u.end());
v.erase(unique(v.begin(), v.end()), v.end());
u.erase(unique(u.begin(), u.end()), u.end());
cout << -1 << " ";
for(int i=0; i<v.size(); i++) cout << v[i] << " ";
cout << "\n";
for(int i=0; i<u.size(); i++) {
cout << u[i] << " ";
for(int j=0; j<v.size(); j++) cout << m[{v[j], u[i]}] << " ";
cout <<"\n";
}
}
백준 BOJ 24771번 : Un-bear-albe Zoo
문제 난이도 : Silver IV
알고리즘 분류 : 트리를 사용한 집합과 맵
N개의 동물의 이름이 주어지는데 여러 단어로 이루어진 입력이고, 마지막 단어만이 동물의 종을 나타내며 이들은 대소문자가 섞여서 나올 수 있다고 할 때, 최종적으로 나온 동물들과 이들의 수를 구하는 문제이다.
map을 사용하여 각 이름들에 대한 개수를 저장해주면 된다.
문제는 동물의 이름 중간에도 대문자가 섞여 나올 수 있으므로 각 이름의 모든 문자에 대해 대문자 여부를 검사해주어 바꿔주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int t=1; ; t++) {
int N; cin >> N;
if(N == 0) break;
cin.ignore();
map<string, int> m;
vector<string> v;
while(N--) {
string str; getline(cin, str);
string name = "";
for(int i=str.length()-1; i>=0; i--) {
if(str[i] == ' ') break;
name = str[i] + name;
}
for(int j=0; j<name.length(); j++)
if(name[j] >= 'A' && name[j] <= 'Z') name[j] += 'a' - 'A';
m[name]++;
v.push_back(name);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << "List " << t << ":\n";
for(int i=0; i<v.size(); i++)
cout << v[i] << " | " << m[v[i]] << "\n";
}
}
백준 BOJ 6851번 : Snowflakes
문제 난이도 : Silver III
알고리즘 분류 : 트리를 사용한 집합과 맵
N개의 6자리 숫자로 이루어진 배열이 주어지고, 각 배열은 뒤집거나 1칸씩 shift할 수 있다고 할 때, 이러한 이동을 거쳐 서로 같은 6자리 배열 쌍이 존재하는지를 구하는 문제이다.
6자리 shift와 뒤집기를 합치면 총 12개의 배열이 나타날 수 있는데, 이들을 모두 해본 뒤 사전순으로 가장 앞서는 것으로 설정한 뒤 같은 배열이 존재하는지 체크해보면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
map<vector<int>, bool> m;
bool check = false;
while(N--) {
vector<int> v(6);
for(int i=0; i<6; i++) cin >> v[i];
vector<int> w(v);
for(int i=0; i<6; i++) {
vector<int> u;
for(int j=i; j<6; j++) u.push_back(w[j]);
for(int j=0; j<i; j++) u.push_back(w[j]);
v = min(v, u);
}
reverse(w.begin(), w.end());
for(int i=0; i<6; i++) {
vector<int> u;
for(int j=i; j<6; j++) u.push_back(w[j]);
for(int j=0; j<i; j++) u.push_back(w[j]);
v = min(v, u);
}
if(m[v]) {
check = true;
break;
}
m[v] = true;
}
if(check) cout << "Twin snowflakes found.\n";
else cout << "No two snowflakes are alike.\n";
}
백준 BOJ 15237번 : Cipher
문제 난이도 : Silver III
알고리즘 분류 : 해시를 사용한 집합과 맵, 정렬
N개의 수가 주어질 때, 빈도가 높은 수가 먼저 나오고, 같은 빈도인 경우 먼저 나온 수가 앞에 나오도록 정렬할 때 정렬한 배열을 구하는 문제이다.
sort의 cmp 함수를 직접 구현하여 구현해줄 수 있고, cmp 함수에서는 map을 활용하여 return 값을 지정해줄 수 있다.
map으로 각 수의 빈도를 세어주고, 먼저 나오는 것의 여부도 map으로 최초로 나온 idx를 저장해서 확인해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, int> m, idx;
bool cmp(int a, int b) {
if(m[a] != m[b]) return m[a] > m[b];
else return idx[a] < idx[b];
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v;
for(int i=0; i<N; i++) {
int x; cin >> x;
if(m[x] == 0) {
v.push_back(x);
idx[x] = i;
}
m[x]++;
}
sort(v.begin(), v.end(), cmp);
for(int i=0; i<v.size(); i++)
for(int j=0; j<m[v[i]]; j++) cout << v[i] << " ";
cout << "\n";
}
백준 BOJ 22133번 : Олимпиада
문제 난이도 : Silver I
알고리즘 분류 : 포함 배제의 원리
세 직사각형의 가로 세로가 주어질 때 합집합 넓이의 최소를 구하는 문제이다.
포함 배제의 원리로 풀어줄 수 있다.
먼저 세 직사각형의 넓이를 우선 다 더하고, 그 다음 두 직사각형의 겹치는 넓이를 빼주고 (3C2 3쌍), 마지막으로 세 직사각형이 모두 겹치는 넓이를 더해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
while(true) {
int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
if(a*a + b*b + c*c + d*d + e*e + f*f == 0) break;
if(a < b) swap(a, b);
if(c < d) swap(c, d);
if(e < f) swap(e, f);
int ans = a*b + c*d + e*f;
ans -= min(a, c) * min(b, d);
ans -= min(c, e) * min(d, f);
ans -= min(e, a) * min(f, b);
ans += min({a, c, e}) * min({b, d, f});
cout << ans << "\n";
}
}
백준 BOJ 7121번 : Pencil Factory
문제 난이도 : Silver IV
알고리즘 분류 : 포함 배제의 원리
Painting은 N개의 o 이후에 x가 1개씩 나오고, Varnishing은 M개의 o 이후에 x가 1개씩 나온다고 할 때, 1 ~ K 중에서 다음의 4가지를 구하는 문제이다.
1. Painting과 Varnishing이 모두 o인 것의 개수
2. 둘 다 x인 것의 개수
3. Painting만 o인 것의 개수
4. Varnishing만 o인 것의 개수
먼저 N과 M의 최소공배수를 구한 뒤, 포함과 배제의 원리를 이용하여 풀이할 수 있다.
코드를 참고하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
N++, M++;
int lcm = N * M / __gcd(N, M);
cout << K - K/N - K/M + K/lcm << " ";
cout << K/lcm << " ";
cout << K/M - K/lcm << " ";
cout << K/N - K/lcm << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 다양한 해시맵(map) 활용 문제들 solution 220822 (0) | 2022.08.22 |
|---|---|
| 중간에서 만나기 : 밋 인더 미들 알고리즘 풀이 모음 220821 (0) | 2022.08.21 |
| 백준 BOJ 스위핑, 값/좌표 압축 알고리즘 문제 풀이 모음 220819 (0) | 2022.08.19 |
| 백준 BOJ 문제 풀이 모음 : 그래프와 인접 행렬의 활용 220818 (0) | 2022.08.18 |
| 백준 BOJ 빠른 거듭제곱 알고리즘 (인접 행렬 활용 등) 문제 풀이 모음 (0) | 2022.08.17 |