#1269 : 대칭 차집합 (자료구조 Silver 4)
[문제]
[코드 및 결과]
#include <iostream>
#include <map>
using namespace std;
int main() {
int N, M, num;
map<int, bool> m;
cin >> N >> M;
for (int i = 0; i < N + M; i++) {
cin >> num;
if (m[num] == true) {
m.erase(num);
}
else {
m[num] = true;
}
}
cout << m.size() << "\n";
return 0;
}
[설명]
처음에는 집합으로 하려다가 두가지 값을 저장하기 좋은 map이 더 나을 것 같아서 map을 이용하여 풀었다.
두 집합의 원소들을 입력 받아서 대칭 차집합을 구하는 문제이다.
for (int i = 0; i < N + M; i++) {
cin >> num;
if (m[num] == true) {
m.erase(num);
}
else {
m[num] = true;
}
N과 M을 입력받아 N+M만큼 반복하는데, 수를 입력 받을 때마다 이 수가 map에 없으면 m[num]을 true로 바꿔주고, 이미 그 값이 true라면 map에서 그 수를 지워준다.
그 과정이 다 끝나면 남은 원소들만 출력해주면 된다.
#15650 : M과 N (2) (자료구조 Silver 3)
[문제]
[코드 및 결과]
#include <iostream>
using namespace std;
int N, M;
int arr[10];
bool visited[10];
void dfs(int num, int idx) {
if (idx == M) {
for (int i = 0; i < M; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
for (int i = num; i <= N; ++i) {
if (!visited[i]) {
visited[i] = true;
arr[idx] = i;
dfs(i + 1, idx + 1);
visited[i] = false;
}
}
}
int main() {
cin >> N >> M;
dfs(1, 0);
return 0;
}
[설명]
N과 M을 입력 받아 길이가 M인 수열을 출력하는데, 조합이라고 생각하면 편하다.
중복이 없어야하므로 이미 거쳐간 수에 대한 처리가 필요하기 때문에 dfs를 사용해보기로 했다.
이전에 N과 M(1) 문제에서 작성했던 코드랑 별반 다를 게 없는 것 같아서 가져와서 조금 수정했다.
void dfs(int num, int idx) {
if (idx == M) {
for (int i = 0; i < M; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
for (int i = num; i <= N; ++i) {
if (!visited[i]) {
visited[i] = true;
arr[idx] = i;
dfs(i + 1, idx + 1);
visited[i] = false;
}
}
}
이 문제에서는 num, idx 라는 인자를 두개 전달하게 했다.
idx가 M과 같다면 배열에 저장된 값을 쭉 출력하도록 했다.
아래는 수열을 구하는 과정인데, 만약 i를 방문하지 않았다면 true로 상태를 바꿔주고 arr[idx]값을 i로 바꿔준 뒤에 재귀함수로 다시 dfs 함수로 들어가도록 했다. 이를 거친 후에는 다시 상태를 false로 바꿔주었다.
이렇게 끝까지 다 돌면 우리가 원하는 중복 없는 수열을 뽑아서 출력해낼 수 있게 된다.
#13417 : 카드 문자열 (자유 Silver 4)
[문제]
[코드 및 결과]
#include <iostream>
#include <deque>
using namespace std;
int main() {
int T, N;
char c;
cin >> T;
for (int i = 1; i <= T; i++) {
deque<char> dq;
cin >> N;
for (int j = 0; j < N; j++) {
cin >> c;
if (j == 0) {
dq.push_back(c);
}
else if (c <= (dq.front())) {
dq.push_front(c);
}
else {
dq.push_back(c);
}
}
for (int j = 0; j < dq.size(); j++) {
cout << dq[j];
}
cout << "\n";
}
return 0;
}
[설명]
N장의 카드 중에서 맨 앞에 있는 카드를 가져오고, 그 후부터는 맨 앞에 오는 카드들을 가져온 카드 맨 앞이나 맨 뒤에 붙여서 문자열을 만드는데, 그 중에서 사전 순으로 가장 앞에 오는 문자열을 구하면 된다.
앞이나 뒤에 삽입하기 좋게 여기서는 deque를 사용했다.
for (int j = 0; j < N; j++) {
cin >> c;
if (j == 0) {
dq.push_back(c);
}
else if (c <= (dq.front())) {
dq.push_front(c);
}
else {
dq.push_back(c);
}
}
반복문으로 문자를 입력받으면서 처리를 하는데, 사전 순으로 가장 앞에 오려면 카드더미에서 가져오는 카드가 현재 내 앞에 있는 카드보다 사전순으로 빠르면 앞에 두고, 느리면 뒤로 두는 식으로 처리를 해주면 된다.
이렇게 해서 만들어진 deque를 최종적으로 출력해주면 된다.
'C++ > Baekjoon' 카테고리의 다른 글
[BOJ] 2022 SISS 2학기 스터디 - 4주차 (0) | 2022.10.02 |
---|---|
[BOJ] 2022 SISS 2학기 스터디 - 2주차 (0) | 2022.09.18 |
[BOJ] 2022 SISS 2학기 스터디 - 1주차 (0) | 2022.09.11 |
[BOJ] #1302. 베스트셀러 (0) | 2022.08.07 |
[BOJ] #1065. 한수 (0) | 2022.07.31 |
댓글