[99클럽/코딩테스트 챌린지/C++] 카드 문자열 문제에서 사전 순 최소 문자열을 구성하는 방법

문제 링크 : 

https://www.acmicpc.net/problem/13417

문제 설명

태욱이는 일렬로 놓인 N장의 카드에서 차례대로 카드를 가져와서 왼쪽 또는 오른쪽에 배치해 가장 사전 순으로 빠른 문자열을 만들고자 한다. 각 테스트 케이스마다 초기 카드 순서가 주어지며, 목표는 이 카드들로 만들 수 있는 가장 작은 사전 순 문자열을 출력하는 것이다.

접근법

처음에는 그리디 알고리즘이 필요하다는 점을 명확히 인식하지 못했으나, 문제를 분석하면서 각 단계에서 최적의 선택을 해야 한다는 점을 깨달았다. 이를 통해 매 순간 왼쪽 또는 오른쪽에 카드를 배치하여 사전 순으로 가장 빠른 선택을 반복하는 것이 필요하다는 결론에 도달했다.

1. 비교: 현재 카드를 이미 배치한 문자열의 첫 번째 문자와 비교한다.
2. 배치: 사전 순으로 빠르게 하려면, 현재 카드가 첫 문자보다 작거나 같다면 왼쪽에, 더 크다면 오른쪽에 배치한다.

코드

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <map>
#include <queue>

using namespace std;

int main() {
	int T = 0;
	int N = 0;

	std::cin >> T;
	while (T > 0)
	{
		std::cin >> N;
		vector<char> str;
		char temp = ' ';
		for (size_t i = 0; i < N; i++)
		{
			std::cin >> temp;
			if (str.size() <= 0) {
				str.push_back(temp);
			}
			else
			{
				if (str[0] < temp) {
					str.push_back(temp);
				}
				else
				{
					str.insert(str.begin(), temp);
				}
			}
		}
		for (char c : str) {
			std::cout << c;
		}
		std::cout << '\n';
		T--;
	}

	return 0;
}

결론

이 문제는 각 단계에서 사전 순으로 가장 빠른 선택을 반복하는 방식으로 해결해야 했다. 매 순간 최적의 선택을 함으로써 문제를 효과적으로 풀 수 있었고, 이 경험을 통해 문자열 문제에서도 그리디 알고리즘의 중요성을 다시 한 번 체감할 수 있었다.