A - Hamming Distance
문제 설명
두 문자열 S와 T가 주어졌을 때, 서로 다른 문자의 개수를 구한다.
풀이 방법
문자열을 순회하며 각 위치의 문자가 다를 때마다 카운트를 증가시킨다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s, t;
cin >> n >> s >> t;
int diffCount = 0;
for (int i = 0; i < n; i++) {
if (s[i] != t[i]) {
diffCount++;
}
}
cout << diffCount << '\n';
return 0;
}
B - Ranking with Ties
문제 설명
N명의 점수가 주어졌을 때, 동점자를 같은 등수로 처리하여 등수를 출력한다.
풀이 방법
점수와 원래 인덱스를 쌍으로 저장한 후 점수 내림차순으로 정렬한다. 동점인 경우 같은 등수를 부여하고, 그렇지 않으면 이전까지의 등수에 동점자 수를 더한다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> scores(n);
for (int i = 0; i < n; i++) {
cin >> scores[i].first;
scores[i].second = i;
}
sort(scores.begin(), scores.end(), greater<>());
vector<int> ranks(n);
int currentRank = 1;
int tieCount = 1;
ranks[scores[0].second] = currentRank;
for (int i = 1; i < n; i++) {
if (scores[i].first == scores[i - 1].first) {
tieCount++;
ranks[scores[i].second] = currentRank;
} else {
currentRank += tieCount;
ranks[scores[i].second] = currentRank;
tieCount = 1;
}
}
for (int i = 0; i < n; i++) {
cout << ranks[i] << '\n';
}
return 0;
}
C - Make it Forest
문제 설명
N개의 정점과 M개의 간선으로 이루어진 그래프가 주어졌을 때, 최소 개수의 간선을 제거하여 숲(사이클이 없는 그래프)을 만든다.
풀이 방법
Union-Find 자료구조를 사용하여 간선을 순회한다. 두 정점이 이미 같은 집합에 속해 있다면 해당 간선은 사이클을 형성하므로 제거해야 하며, 그렇지 않으면 두 집합을 병합한다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> parent, size;
UnionFind(int n) : parent(n), size(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (size[x] < size[y]) swap(x, y);
parent[y] = x;
size[x] += size[y];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
UnionFind uf(n + 1);
int removedEdges = 0;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if (!uf.unite(u, v)) {
removedEdges++;
}
}
cout << removedEdges << '\n';
return 0;
}
D - Switch Seats
문제 설명
길이가 2N인 순열이 주어지며, 각 숫자는 정확히 두 번 등장한다. 두 쌍 (a, b)에 대해 a의 두 위치와 b의 두 위치가 각각 인접해 있고, a의 두 위치 사이 또는 b의 두 위치 사이에 다른 숫자가 없을 때 조건을 만족한다. 이러한 쌍의 개수를 구한다.
풀이 방법
각 숫자의 첫 번째와 두 번째 등장 위치를 저장한다. 위치 쌍을 첫 번째 등장 위치 기준으로 정렬한 후 인접한 쌍을 확인한다. 두 쌍의 첫 번째 위치가 1 차이 나고 두 번째 위치도 1 차이 나며, 각 숫자의 두 위치가 인접하지 않은 경우에만 카운트를 증가시킨다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases;
cin >> testCases;
while (testCases--) {
int n;
cin >> n;
n *= 2;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<pair<int, int>> positions;
vector<int> firstPos(n / 2 + 1, -1);
for (int i = 0; i < n; i++) {
if (firstPos[arr[i]] == -1) {
firstPos[arr[i]] = i;
} else {
positions.emplace_back(firstPos[arr[i]], i);
}
}
sort(positions.begin(), positions.end());
int pairCount = 0;
for (int i = 0; i < (int)positions.size() - 1; i++) {
auto [firstA, secondA] = positions[i];
auto [firstB, secondB] = positions[i + 1];
if (secondA - firstA == 1 || secondB - firstB == 1) continue;
if (abs(firstA - firstB) != 1 || abs(secondA - secondB) != 1) continue;
pairCount++;
}
cout << pairCount << '\n';
}
return 0;
}
E - Replace
문제 설명
주어진 문자열과 변환 규칙을 사용하여 목표 문자열을 만드는 최소 비용을 구한다. 각 변환은 특정 문자를 다른 문자로 바꾸거나, 특정 문자를 문자열로 치환하는 형태로 주어진다.
풀이 방법
이 문제는 다이나믹 프로그래밍 또는 최단 경로 알고리즘을 사용하여 해결할 수 있다. 각 문자에서 다른 문자 또는 문자열로의 변환 비용을 고려하여 최소 비용을 계산한다.
코드 보기
// 추후 작성 예정