취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1294번 문제인 문자열 장식이다.
문제는 아래 링크를 확인하자.

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

결론을 쓰면, 두 문자열 s1, s2가 있을 때, 두 문자열 중 s1+s2가 s2+s1보다 사전순으로 빨리 온다면 s1의 첫 글자를 먼저, 그렇지 않다면 s2의 첫 글자를 먼저 이용하는 것이 항상 이득이다.

두 문자열 s1, s2에 대하여 s1+s2 < s2+s1 형태의 문자열 비교 연산은 문자열 사이에 strict order을 부여함이 잘 알려져있다. 즉, 세 문자열 s1, s2, s3에 대해서 s1+s2<s2+s1, s2+s3<s3+s2가 성립하면 s1+s3<s3+s1 또한 성립한다는 의미이다. 따라서 이러한 비교 연산을 이용해 문자열에 순서를 부여하는 것으로 문제를 해결할 수 있다.

위 내용에 대한 글을 작성하게 되면 이곳에 링크를 남겨두겠다.

아래는 제출한 소스코드이다.

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

struct comp {
	bool operator() (string& s1, string& s2) {
		return (s1 + s2 > s2 + s1);
	}
};
priority_queue<string,vector<string>,comp> pq;

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

	int N; cin >> N;
	while (N--) {
		string s; cin >> s;
		pq.push(s);
	}

	while (!pq.empty()) {
		string cur = pq.top(); pq.pop();
		cout << cur[0];
		int curlen = cur.length();
		if (curlen > 1) pq.push(cur.substr(1, curlen - 1));
	}
}