[BOJ 10546] 배부른 마라토너

2021년 5월 3일

문제는 여기서 풀 수 있습니다.

문제 요약

$N$ 개의 이름이 입력되고 그 뒤 $N$ 개의 이름 중 $N - 1$ 개의 이름이 다시 입력됩니다.

이 때 다시 입력되지 않은 이름 한 개를 찾는 문제입니다.

문제 풀이

1. 문제에서 시키는 대로 하기

$set$ 에 처음에 주어지는 $N$ 개의 이름을 저장합니다. 그 다음 주어지는 $N - 1$ 개의 이름을 $set$ 에거 제거합니다. 동명이인이 있을 수 있기에 $multiset$ 을 이용하면 문제를 쉽게 풀 수 있습니다.

시간 복잡도는 $O(L \times N \times logN)$ 입니다. 여기서 $L$ 은 문자열의 최대 길이를 의미합니다.

#include <stdio.h>
#include <string>
#include <set>

using namespace std;

int n;
char name[30];
multiset<string> S;

int main() {
	scanf("%d", &n);

	for (int i = 0 ; i < n ; ++i) {
		scanf("%s", name);
		S.insert(name);
	}

	for (int i = 0 ; i < n - 1 ; ++i) {
		scanf("%s", name);
		auto it = S.find(name);
		S.erase(it);
	}

	printf("%s\n", S.begin()->c_str());
}

2. 조건을 한번 더 생각해 보기

문제에서는 $N$ 명의 이름과 주어지고 그중 한 명을 제외한 이름들이 다시 주어집니다. 이때 주어지지 않은 이름의 첫 번째 알파벳은 어떤 걸까요? 입력으로 주어진 $2 \times N - 1$ 개의 이름들 중 첫 번째 알파펫들이 등장하는 횟수를 모두 기록합니다. 대부분의 알파벳들은 짝수 번 등장하거나 한 번도 등장하지 않았지만 단 한 개의 알파벳은 홀수 번 등장했을 것입니다. 바로 그 알파벳이 주어지지 않은 이름의 첫 번째 알파벳이 됩니다. 이를 확장해서 모든 글자에 적용하면 정답을 찾을 수 있습니다.

풀이는 입력된 알파벳들을 세는 부분과 답을 구하는 부분으로 나눠집니다. 첫 번째 부분은 $L \times N \times A$ 입니다. 여기서 A는 알파벳의 갯수를 의미합니다. $L$ 과 $A$ 가 크지 않기 때문에 충분히 시간내에 들어올 수 있습니다. 두 번째 부분은 $L \times A$ 인데 첫 번째에 비해 무시할 수 있을만큼 작으므로 이 풀이의 시간 복잡도는 $O(L \times N \times A)$ 라고 할 수 있습니다.

#include <stdio.h>

int n, cnt[30][26];
char name[30];

int main() {
	scanf("%d", &n);
	for (int i = 0 ; i < n * 2 - 1 ; ++i) {
		scanf("%s", name);

		for (int j = 0 ; name[j] != '\0' ; ++j) {
			++cnt[j][name[j] - 'a'];
		}
	}

	for (int i = 0 ; i < 30 ; ++i) {
		for (int j = 0 ; j < 26 ; ++j) {
			if (cnt[i][j] % 2 == 1) {
				printf("%c", j + 'a');
			}
		}
	}
}

3. 비트 연산자를 이용하기

홀수 번 등장하는 알파벳이 정답이라는 것을 본 순간 눈치를 챘을수도 있지만 이 문제는 $xor$ 연산자를 이용하면 간결하고 우아하게 코딩을 할 수 있습니다. 똑같은 비트를 $xor$ 하면 0이 되는 특징을 이용하는 것입니다. 이 풀이의 시간 복잡도는 $O(L \times N)$ 으로 가장 빠른 시간 복잡도를 가졌습니다.

#include <stdio.h>

int n;
char name[30], ans[30];

int main() {
	scanf("%d", &n);

	for (int i = 0 ; i < n * 2 - 1 ; ++i) {
		scanf("%s", name);

		for (int j = 0 ; name[j] != '\0' ; ++j) {
			ans[j] ^= name[j];
		}
	}

	printf("%s\n", ans);
}