[BOJ 1294] 문자열 장식

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

1294번: 문자열 장식

 

- 문제 요약

 

오민식은 단어 N(N<=20)개를 이용해서 문자열 W를 만들려고 한다.

일단 오민식은 각각의 문자열을 적절히 쪼갠다. 그다음에 쪼갠 문자열을 모두 이어 붙여서 W를 만든다. 단, 한 문자열을 쪼개서 나온 조각의 순서는 유지해야 한다.

예를 들어, 오민식이 {YOUNGSIK, DONGHO, BAEKJOON} 총 3개를 가지고 있었다면, 오민식은 자기 마음대로 {YOUNG, SIK, DO, NG, HO, BA, E, K, JOO, N}과 같이 쪼갠 다음, 아래와 같이 YOUNGDOBAESIKNGKJOOHON을 만들 수 있다.

예시

오민식이 만들 수 있는 문자열 중에 사전순으로 가장 앞서는 것을 출력하시오.

 

 

- 알고리즘 정리

 

문자열 s1 뒤에 s2 문자열을 이은 것을 문자열 S12라고 하고, s2 뒤에 s1을 이은 것을 S21이라 하겠습니다.

이 둘을 사전순으로 비교해서 S12가 S21보다 앞선다면 s1의 0번째 글자를, S21이 S12보다 앞선다면 s2의 0번째 글자를 출력해 줍니다.

이런 식으로 우선순위를 따져가며 그리디 하게 문제를 해결해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	while(n--){
		cin>>s;
		pq.push(s);
	}
	while(!pq.empty()){
		string Top=pq.top();
		pq.pop();
		cout<<Top[0];
		int Size=Top.length();
		if(Size>1){
			pq.push(Top.substr(1,Size-1));
		}
	}
}

코드 제출 결과