관심이 가는 개발 보물창고

[문제풀이]

문자열 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;
}

이번에는 foreach문에 대해서 공부해보겠습니다.

foreach 문이 왜 등장했을까요? 기존에 for, while, do~while 문으로 대체가 가능한데..

그러다가 어떤 한 블로그의 말을 듣고 납득이 되었습니다.

그 말은 foreach문은 index범위를 벗어나는 위험성이 없다는 것입니다.

무슨말이냐면, 배열이나 컬렉션의 끝에 도달하면 자동으로 반복이 종료하게 되는데요.

만약에 foreach문을 사용하지 않고 기존에 알고 있었던 for문을 이용해서 구현했더라면 프로그래머의 실수로 인해 할당되지 않은 영역을 참조하는 경우가 발생할 수 있습니다.

이러한 경우가 바로 IndexOutOfRangeException 입니다.

정확히는 해당 범위 외부에 있는 인덱스를 사용해서 배열 또는 컬렉션의 요소에 액세스하려고 할 때 발생하는 오류입니다.

가끔 개발을 하다보면 나도 모르게 index범위를 잘못 설정하여 프로그램이 오류로 인해 돌아가지 않는 경우가 빈번합니다.

큰 개발일수록 이러한 작은 실수를 줄이기 위해서 등장한 것이 바로 foreach문입니다.

다만 foreach문도 단점이 있습니다.

다른 반복문에 비해 3~4배 정도 느리다고 합니다.

하지만 이러한 문제 때문에 짜잘한 부분에서 퍼포먼스를 줄이는 것보다는 병목현상이 발생하는 부분을 찾아서 개선하는 것이 전체 프로젝트의 퍼포먼스를 올린다는 것을 명심해야 합니다. 게다가 사람은 언제나 실수를 하기 때문이죠.

주저리 주저리 설명이 길었는데 이제 foreach문을 어떻게 사용하는지 알아봅시다.

foreach(데이터타입 변수명 in 배열(컬렉션)
{
     // to-do
}

배열 혹은 컬렉션의 요소를 차례대로 순회하면서 in 키워드 앞에 있는 변수에 담아줍니다.

다만 박싱(언박싱) 부분만 주의해서 사용한다면 좋을 것 같습니다.

using System;

class Program
{
    static void Main(string[] args)
    {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6 };

        foreach(int n in arr)
        {
            Console.WriteLine(n);
        }
    }
}

1
2
3
4
5
6

null 병합 연산자란?

null 병합 연산자는 ?? 입니다.

?? 는 null 조건부 연산자처럼 객체나 변수의 null 검사를 간결하게 해 줍니다.

두 개의 피연산자를 받아들이고

왼쪽 피연산자가 null이라면 오른쪽 피연산자를 반환합니다.

왼쪽 피연산자가 null이 아니라면 왼쪽 피연산자를 반환합니다.

이번에 C#을 공부하면서 느낀 건 null과 관련된 형식에는? 기호가 들어갑니다.

Nullable, ?. , ?[]도?로 시작합니다.

C, C++에서는 경험하지 못한 새로운 문법입니다.

말보다는 한 번 보는 것이 이해가 잘 된다고 생각합니다.

int? num = null;
Console.WriteLine($"{num ?? 0}"); // num이 null이기 때문에 0이 출력됩니다.

string str = "hi";
Console.WriteLine($"{str ?? "default"}"); // str은 null이 아니기 때문에 hi가 출력됩니다.

연습 예제

using System;

class Program
{
    static void Main(string[] args)
    {
        int? num = null;
        Console.WriteLine($"{num ?? 0}");

        num = 2021;
        Console.WriteLine($"{num ?? 0}");

        string str = null;
        Console.WriteLine($"{str ?? "Default"}");

        str = "Arcane";
        Console.WriteLine($"{str ?? "Default"}");
    }
}

실행결과

0
2021
Default
Arcane

문제 풀이

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

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;
}