[백준] 3048 개미 C++

https://www.acmicpc.net/status?user_id=starkshn&problem_id=3048&from_mine=1

 

처음에 문제를 읽고 아 "left, right라는 개념을 두고 swap을 2번씩 수행하면 되겠다!"라는 아이디어로 출발했다가 다시 생각하게 만든 문제이다.

 

우선 "그룹"을 나눌 필요가 있고, 개미 그룹이 다른 그룹을 만난 경우 스왑을 해야한다.

이 그룹을 나누는 방법에서 코드의 차이가 있는데, 그룹을 나누고 나누어진 그룹끼리 같은 "초"안에 스왑을 통해서 자리를 변경해주면된다.

 

그룹을 나누는 방법은 여러가지인데 본인은 unordered_set을 통해서 그룹을 나누었다.

g1, g2라는 그룹을 나누고 전체 문자열 s에서 g1에는 포함되어 있는 문자가 g2에는 포함되어 있지 않으면 같은 초 내에서 두 문자열을 스왑해주어야한다.

 

말이 어려우니 코드를 보도록하자.

 

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int s1, s2, T;
	string a, b;
	cin >> s1 >> s2;
	cin >> a >> b;
	cin >> T;

	reverse(a.begin(), a.end());
	string s = a + b;

	unordered_set<char> g1;
	for (char c : a) g1.insert(c);

	int n = (int)s.size();
	while (T--)
	{
		for (int i = 0; i < n - 1; )
		{
			// i가 1그룹이고, i + 1가 2그룹이라면 swap
			if (g1.count(s[i]) && !g1.count(s[i + 1]))
			{
				swap(s[i], s[i + 1]);
				i += 2;
			}
			else i++;
		}
	}

	cout << s << endl;

	return 0;
}

 

현재 초에서 다른 그룹의 개미를 만나면 스왑하는 식이 if (g1.count(s[i]) && !g1.count(s[i + 1])) 로 들어가있다.

 

해당 문제를 통해 그룹을 어떻게 나누고 그룹에 포함식을 어떻게 세운것인지 기억하도록 하자.