김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
[입력] 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
[출력] 듣보잡의 수와 그 명단을 사전순으로 출력한다.
✅ 문제 풀이
set 자료구조에 입력받은 이름들을 저장할건데, 듣도 못한 사람들을 입력받고 저장해둔다.
그리고 보도 못한 사람들을 입력받을 때마다, set의 find함수를 사용해서, 보도 못한 사람이 있는지 확인하고, 있으면 vector에 저장한다.
마지막에 vector의 크기를 출력하고, 사람을 사전 순으로 출력해야 하므로 sort함수를 통해 오름차순 정렬한다.
그리고 정렬된 vector의 내용을 모두 출력한다.
✏ 코드 전문
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
set<string> arr;
for (int i = 0; i < n; i++) {
string str;
cin >> str;
arr.insert(str);
}
vector<string> answer;
for (int i = 0; i < m; i++) {
string str;
cin >> str;
auto it = arr.find(str);
if (it != arr.end()) answer.push_back(str);
}
cout << answer.size() << "\n";
sort(answer.begin(), answer.end());
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << "\n";
}
return 0;
}
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
✅ 문제풀이
간단하게 queue를 이용
queue에 1부터 N까지 값을 차례로 넣은 후, 앞에서부터 K-1번 빼서 뒤로 다시 넣는다.
그럼 K번째 값이 queue의 맨 앞에 위치하게 되고, 해당 값을 answer에 넣어주고, queue에서 삭제한다.
위 과정을 queue의 크기가 1이 될때까지 반복한다.
queue에 하나의 값만 남게 되면, 그 값을 answer에 넣어준다.
그리고 출력 형식에 맞게, answer에 있는 값을 차례로 출력해주면 된다.
아래 그림처럼 동작하게 된다. (예제로 예를 들어보자)
1. queue에 1부터 7까지 넣은 모습이다.
2. 3번 째 값을 제거하기 위해서 앞에서부터 뒤로 넘겨주어야 한다.
1번 째 값을 queue에서 pop하고, 다시 동일한 queue에 push하여 뒤로 넘어가게 한다.
3. 2번 째 값을 queue에서 pop하고, 다시 동일한 queue에 push하여 뒤로 넘어가게 한다.
4. 드디어 3(=K)번 째 값에 도달했으니, 이 값은 answer에 넣어주고, queue에서 삭제해준다.
5. 위의 과정을 아래 queue의 길이가 1이 될 때까지(=마지막 하나만 남을때까지) 반복해주면 된다.
최종 코드는 아래와 같다.
#include<iostream>
#include<queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, K;
cin >> N >> K;
queue<int> q;
queue<int> answer;
for (int i = 1; i <= N; i++) {
q.push(i);
}
while (q.size() > 1) {
for (int i = 1; i < K; i++) {
int temp = q.front();
q.pop();
q.push(temp);
}
answer.push(q.front());//k번 째 빼기
q.pop();
}
answer.push(q.front());
q.pop();
cout << "<"<<answer.front();
answer.pop();
while (!answer.empty()) {
cout << ", " << answer.front();
answer.pop();
}
cout << ">";
}
