관심이 가는 개발 보물창고

[문제풀이]

문자열 A와 문자열 B가 주어졌을 때, 항상 A의 길이는 B의 길이보다 작거나 같은 조건에서 입력으로 주어졌을 때

A와 B의 길이가 같으면서도, A와 B의 차이를 최소가 되도록 하는 방법을 구하는 문제입니다.

채워 넣을 때는 아무거나 알파벳을 넣되 앞에서 넣나 뒤에서 넣나 최선의 방법으로 넣어야 우리는 최소의 경우를 구할 수 있습니다. 최선의 경우가 아니면 더 많은 방법으로 돌아가겠죠.

간단하게 주어진 입력에 대해서 비교를 하면 쉽습니다.

어처피 채워 넣는 건 최선의 방법으로 채워 넣기 때문에 기존에 입력된 부분의 차이만 구하면 그 차이가 바로 최소의 차이이기 때문입니다.

A : adaabc

B : aababbc

어릴 때 모양이 여러 조각 난 판이 있을 때 그 모양에 끼워넣기 위해서 이리저리 놓아서 넣는 경험을 해본 적이 있을 겁니다. 이를 똑같이 문제에 적용하면 B라는 판에 A라는 조각을 이리저리 끼워 넣어 보고 차이를 구하면 됩니다.

aababbc

adaabc

이렇게 끼워 넣어 보면 3군데가 차이가 됩니다.

그러면 다른 방법으로 끼워봅시다. (약간 삐뚤긴 했지만.. 잘 보면 2군데가 차이가 됩니다.)

aababbc

  adaabc

어떤가요? 2군데 차이를 기준으로 채워 넣는 건 최선의 방법으로 넣으니까 결국 답은 2라는 것을 알 수 있습니다.

정리하면 B라는 문자열에 A라는 작은 문자열을 이리저리 껴놓고 틀린 차이만 카운팅 해서 최소한으로 갱신해주면 문제를 해결할 수 있게 됩니다.

더 있을까요?

아닙니다. A라는 문자열을 저희가 늘리거나 줄일 수 있는 방법이 없기 때문에 총 2가지 케이스에 대해서만 생각할 수 있습니다.

이를 어떻게 구현할까요?

되도록이면 일단 해보고 그래도 모르겠다면 아래의 풀이를 봐주시면 좋겠습니다.

이런 문제가 약간 실력의 향상의 밑거름이라고 생각되는 좋은 문제입니다!

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	string a, b;
	cin >> a >> b;
	int ans = b.size();
	int len = b.size() - a.size();
	for (int i = 0; i <= len; i++)
	{
		int cnt = 0;
		for (int j = 0; j < a.size(); j++)
		{
			if (a[j] != b[i + j])
				cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

문제 풀이

기존의 에라토스테네스의 체에서 약간 변형의 문제입니다.

보통은 소수를 제외하고 그 소수의 배수를 모두 지우는 형태가 에라토스테네스의 체 구현이지만, 이 문제에서 요구하는 건 소수를 찾았을 때도 제거하고 그의 배수들도 모두 제거하면서 지나갑니다.

N = 7, K = 3이면

제거하는 순서를 나열하면 다음과 같습니다.

2 4 6 (2의 배수) 3 (3의 배수) 5 (5의 배수) 7 (7의 배수)

따라서 3번째 제거된 수는 6입니다.

중복되는 수를 제거 방지를 위해서 prime변수를 선언해서 제거했더라면 false로 시키고 카운팅 합니다.

카운팅 횟수가 K번째와 같게 된다면 그때가 바로 K번째로 제거된 수입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
bool prime[1001];

void eratosthenes()
{
	fill(prime, prime + 1001, true);
	prime[0] = false;
	prime[1] = false;

	int cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		// i의 수를 아직 안지웠다면?
		if (prime[i] == true)
		{
			cnt++;
			prime[i] = false;
			if (cnt == k)
			{
				cout << i << endl;
				return;
			}
		}
		// i의 배수를 모두 확인
		for (int j = i + i; j <= n; j += i)
		{
			// j 수를 아직 안지웠다면?
			if (prime[j] == true)
			{
				cnt++;
				prime[j] = false;
				if (cnt == k)
				{
					cout << j << endl;
					return;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	eratosthenes();
	return 0;
}

문제 풀이

덩치를 정하는 방법은 (a1, b1) (a2, b2)가 있을 때 a1 > a2 이면서 b1 > b2 이면 앞에 있는 사람이 뒤에 있는 사람보다 덩치가 크다는 의미입니다.

그런데 덩치를 정할 수 없는 순간이 있다면 등수는 모두 같은 것으로 치고, 자신보다 앞에 있는 덩치가 N명이라면 자신의 등수는 N+1로 설정하면 됩니다.

N의 크기가 엄청 작기 때문에 완전 탐색으로 모든 경우의 수를 돌려 자신보다 덩치가 큰 녀석들만 카운트합니다.

최종적으로 자신의 등수는 카운트 + 1로 설정합니다. 자신보다 더 큰 덩치가 없다면 자신이 제일 크기 때문에 1등으로 처리해야 되기 때문이죠.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vector<pair<int, int> > v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i].first >> v[i].second;
	}

	for (int i = 0; i < n; i++)
	{
		int count = 0;
		for (int j = 0; j < n; j++)
		{
			if (i == j) continue;
			if (v[i].first < v[j].first && v[i].second < v[j].second)
			{
				count++;
			}
		}
		cout << count + 1 << ' ';
	}

	cout << endl;
	return 0;
}

문제 풀이

빙글빙글 돌면서 K번째 사람을 퇴출하는 방식으로 뽑아내면 되는 문제입니다.

N = 7, K = 3이면

1, 2, 3, 4, 5, 6, 7 사람 중에서 3번째 사람을 뽑는 방식으로 진행합니다.

아래의 빨간 표시는 퇴출하는 사람의 순서입니다.

퇴출하고 나서 다음부터 다시 카운트를 시작합니다.

<3, 

<3, 6,

<3, 6, 2,

<3, 6, 2, 7,

<3, 6, 2, 7, 5, 

<3, 6, 2, 7, 5, 1, 

<3, 6, 2, 7, 5, 1, 4>

이러한 원리로 뽑으려면 앞에서 뽑고 뒤에서 넣는 형태이기 때문에, 큐 자료구조를 이용하면 쉽게 구현할 수 있습니다.

K = 3이면 1, 2번은 뽑아서 다시 뒤에 넣고, 3번째는 뽑아서 출력하고 큐에서 지워주면 됩니다.

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	queue<int> q;
	for (int i = 1; i <= n; i++) q.push(i);

	vector<int> ans;
	while (!q.empty())
	{
		for (int i = 0; i < k - 1; i++)
		{
			q.push(q.front());
			q.pop();
		}
		ans.emplace_back(q.front());
		q.pop();
	}

	cout << "<";
	for (int i = 0; i < ans.size() - 1; i++)
	{
		cout << ans[i] << ", ";
	}
	cout << ans[ans.size() - 1] << ">\n";
	return 0;
}

문제 풀이

알고 보면 쉬운 문제이지만, 생각보다 오래 걸렸습니다.

3개의 점이 주어졌을 때, 좌표 상에서 직사각형을 만들기 위해 남은 나머지 점을 출력하는 문제입니다.

처음에는 각 점 사이의 거리를 구해서 두 개의 거리를 이용해 좌표를 찾으려고 했지만 너무 많은 계산이 들어가서 다시 생각해봤습니다.

연관점을 찾다 보니 x좌표, y좌표마다 2개씩 같고, 1개씩은 따로 노는 점을 발견했습니다.

1개씩 짝이 없는 좌표가 바로 우리가 찾는 네 번째 점이라는 점을 착안하여 map을 이용해서 짝의 개수를 카운트했고,

짝이 없는 좌표만 저장해서 출력하는 방법으로 풀었습니다.

이후에 다른 풀이를 봤는데, 더 간단한 방법이 있었습니다.

x1, x2, x3

y1, y2, y3

이렇게 주어졌을 때 x1 == x2 이면, x3 가 우리가 찾는 좌표고, 다르다면 x2

y1 == y2 이면, y3 다르다면 y2

이렇게 푸는 방법도 있습니다.

소스 코드

#include <iostream>
#include <cmath>
#include <map>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	map<int, int> mx, my;
	for (int i = 0; i < 3; i++)
	{
		int x, y;
		cin >> x >> y;
		mx[x]++;
		my[y]++;
	}

	int x, y;
	for (auto i : mx)
	{
		if (i.second < 2)
		{
			x = i.first;
			break;
		}
	}

	for (auto i : my)
	{
		if (i.second < 2)
		{
			y = i.first;
			break;
		}
	}

	cout << x << ' ' << y << endl;
	return 0;
}

문제 풀이

0이 입력되면 최근에 넣었던 수가 지워집니다.

가만 생각해보면, 자료구조의 스택을 떠오르면 쉽게 해결할 수 있습니다.

소스 코드

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	stack<int> st;
	int k;
	cin >> k;
	while (k--)
	{
		int n;
		cin >> n;
		if (n != 0)
			st.push(n);
		else
			st.pop();
	}

	long long ans = 0;
	while (!st.empty())
	{
		ans += st.top();
		st.pop();
	}

	cout << ans << endl;
		
	return 0;
}

문제 풀이

R, G, B라는 영역이 있을 때, 상하좌우로 인접해있는 영역을 구하는 문제입니다.

중요한 점은 적록색약이 아닌 정상인은 R, G, B 구분할 수 있지만 적록색약인 사람은 R과 G를 같은 색깔로 보게 됩니다.

먼저 정상인 부터 구합니다. 상하좌우로 탐색하면서 R, G, B 를 구분하면서 전체 영역의 개수를 구합니다.

그런 후에 다시 방문 배열을 초기화한 후 적록색약인 사람은 R과 G를 같이 볼 수 있도록 하며, 똑같이 상하좌우로 탐색하면서 영역의 개수를 구하면 됩니다.

탐색 알고리즘은 BFS or DFS 중 하나를 선택해서 구현합니다.

저는 BFS를 이용해서 구현했습니다.

아래의 구현에서 적록색약이 아닌 사람과 적록색약인 사람을 구별하기 위해서 파라미터로 ch1, ch2를 선언했습니다.

정상인은 디폴트로 'A' (의미없는 기호)를 넣어서 탐색했고, 적록색약인 사람은 'R'이면 'G'를 'G'이면 'R'을 지정해서 탐색하였습니다.

소스 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

const int dx[] = { 0,0,-1,1 };
const int dy[] = { 1,-1,0,0 };
const int MAX = 101;

int N;
char board[MAX][MAX];
bool visit[MAX][MAX];

void bfs(int x, int y, char ch1, char ch2 = 'A')
{
	queue<pair<int, int> > q;
	q.push({ x,y });
	visit[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (board[nx][ny] == ch1 || board[nx][ny] == ch2)
			{
				if (visit[nx][ny] == false)
				{
					visit[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}
}

void input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < N; j++)
		{
			board[i][j] = s[j];
		}
	}
}

void solve()
{
	input();

	int man = 0, bman = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == false)
			{
				bfs(i, j, board[i][j]);
				man++;
			}
		}
	}

	fill(visit[0], visit[0] + MAX * MAX, false);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == false)
			{
				if (board[i][j] == 'R')
				{
					bfs(i, j, board[i][j], 'G');
				}
				else if (board[i][j] == 'G')
				{
					bfs(i, j, board[i][j], 'R');
				}
				else
				{
					bfs(i, j, board[i][j]);
				}
				bman++;
			}
		}
	}

	cout << man << ' ' << bman << endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

문제 풀이

각 자리 숫자를 뽑아서 모든 경우의 수를 다 곱해서 정답에 더해주면 됩니다.

문자열로 입력받은 후 각 자리 숫자로 변환한 다음에 계산하면 됩니다.

다만 주의할 점은 정답을 저장할 때 범위를 long long으로 해줘야 합니다.

소스 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string a, b;
	cin >> a >> b;

	long long ans = 0;
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			int n1 = a[i] - '0';
			int n2 = b[j] - '0';
			ans += n1 * n2;
		}
	}

	cout << ans << endl;
	return 0;
}

문제 풀이

문자열이 주어졌을 때 이를 적절하게 섞어서 팰린드롬을 만들 수 있다면, 만들 수 있는 경우에서 사전 순으로 가장 앞서는 문자열을 출력하는 문제입니다.

예제 입력을 잘보면 규칙을 찾을 수 있습니다.

주어진 문자열의 길이가 짝수이면? 팰린드롬을 만들려면 해당 알파벳이 모두 짝수개여야 합니다.

만일 홀수개가 존재한다면 그건 어떤 방법을 사용해도 절대 만들 수 없습니다.

주어진 문자열의 길이가 홀수이면? 팰린드롬을 만들 때 가운데 홀수 알파벳을 제외하고 나머지는 모두 짝수개의 알파벳을 가지고 있어야 만들 수 있습니다. 주의할 점은 홀수 알파벳이 두 개 이상 존재한다면 역시 만들 수 없습니다.

A B C D 모두 각각 홀수 1개씩 가지지만 절대 팰린드롬을 만들 수 없는 것처럼 말이죠.

위에서 걸리는 조건이 있다면 절대 만들 수 없을 것이고, 위의 조건에 위배되지 않는다면?

우리는 가장 사전순으로 빠른 팰린드롬을 만들어야 합니다.

문자열의 길이가 짝수라면 가장 알파벳 사전 순이 뒤에 있는 것부터 안쪽부터 채워나가면 됩니다.

AABB (A가 2개, B가 2개) 이므로
안쪽부터 채워나가면
BB
ABBA

만약에 문자열의 길이가 홀수라면? 홀수 알파벳을 먼저 가운데에 채워 넣고, 위와 마찬가지로 사전 순으로 느린 것부터 안쪽을 채워나가면 됩니다.

ABACABA (A가 4개, B가 2개, C가 1개) 이므로
안쪽부터 채워나가면
C
BCB
ABCBA
AABCBAA

안쪽부터 어떻게 채울 수 있을까요? 저는 deque 자료구조를 이용해서 앞이랑 뒤에 알파벳을 넣는 방식으로 구현했습니다.

소스 코드

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int alpha[26];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		alpha[s[i] - 'A']++;
	}

	bool ok = true;
	deque<char> dq;
	if (s.size() % 2 == 0)
	{
		for (int i = 0; i < 26; i++)
		{
			if (alpha[i] > 0 && alpha[i] % 2 != 0)
			{
				ok = false;
				break;
			}
		}

		for (int i = 25; i >= 0; i--)
		{
			int sz = alpha[i] / 2;
			for (int j = 0; j < sz; j++)
			{
				dq.push_back(i + 'A');
				dq.push_front(i + 'A');
			}
		}
	}
	else
	{
		int odd = 0, idx = -1;
		for (int i = 0; i < 26; i++)
		{
			if (alpha[i] > 0 && alpha[i] % 2 != 0)
			{
				odd++;
				idx = i;
			}
		}

		// 주의할 점은 홀수 개는 딱 1개만 존재해야 만들 수 있습니다.
		if (odd > 1 || odd <= 0)
		{
			ok = false;
		}

		dq.push_back(idx + 'A');
		alpha[idx]--;

		for (int i = 25; i >= 0; i--)
		{
			int sz = alpha[i] / 2;
			for (int j = 0; j < sz; j++)
			{
				dq.push_back(i + 'A');
				dq.push_front(i + 'A');
			}
		}
	}

	if (ok == false)
		cout << "I'm Sorry Hansoo\n";
	else
	{
		for (auto c : dq)
		{
			cout << c;
		}
		cout << endl;
	}
	return 0;
}

문제 풀이

검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다고 합니다.

(0,0)이 하얀 칸이면 (0,1)은 검정 칸.. 반복

이랬을 때 규칙을 찾아보면 하얀칸인 좌표는 x + y 가 항상 짝수임을 알 수 있습니다.

따라서 x + y 가  짝수이면서 'F'로 찍힌 곳만 카운팅 해서 출력하면 됩니다. 

소스 코드

#include <iostream>
#include <string>
using namespace std;

char board[8][8];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 8; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
		{
			board[i][j] = s[j];
		}
	}

	int cnt = 0;
	for (int i = 0; i < 8; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0 && board[i][j] == 'F')
				cnt++;
		}
	}

	cout << cnt << endl;
	return 0;
}