[SWEA 1257] K번째 문자열

SWEA 1257번 : K번째 문자열

swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

/* 문제 설명 */

한 문자열이 가진 모든 부분 문자열을 사전 순으로 정렬한다.

이 때, K 번째 문자열을 구하시오.

 

ex) 문자열 love의 모든 부분 문자열 : l, o, v, e, lo,ov, ve, lov, ove, love 

사전 순으로 정렬할 경우 : e, l, lo, lov, love, e, ov, ove, v, ve

 

/* 해결 방안 */

중복되는 경우는 무시해줘야하므로 set을 사용한다.

set에 insert를 하게 될 경우 자동으로 정렬을 해준다.

따라서 O(n^2)만큼, 문자열을 돌면서 부분 문자열을 찾아주고 set에다가 넣어준다.

그러고 나서 set을 iterator로 순회하며 k번째 문자열을 출력한다.

 

/* 구현 과정 */

1. O(n^2)만큼 문자열을 돌면서, 부분 문자열을 찾아준다.

2. 1에서 찾은 부분 문자열을 set에다가 넣어준다.

3. iterator를 돌면서 k번째 문자열을 출력한다.

4. 이 때, k번째 문자열이 없다면 none을 출력한다.

 

/* 소스 코드 */

#include <iostream>
#include <string>
#include <set>
using namespace std;

int TC, k;
string str;

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

	cin >> TC;
	for (int tc = 1; tc <= TC; tc++)
	{
		set<string>s;

		cin >> k >> str;
		for (int i = 0; i < str.size(); i++)
		{
			string temp = {str[i]};
			s.insert(temp);

			for (int j = i + 1; j < str.size(); j++)
			{
				temp += str[j];
				s.insert(temp);
			}
		}

		set<string>::iterator iter;
		int i = 1;
		bool flag = 0;

		cout << "#" << tc << " ";
		for (iter = s.begin(), i = 1 ; iter != s.end(); iter++, i++)
		{
			if (i == k) {
				cout << *iter << "\n";
				flag = 1;
				break;
			}
		}
		if(!flag) cout << "none\n";
	}
}

 

/* 얻어갈 점 */

1. set에 다가 insert를 할 경우 자동으로 정렬을 해준다.

2. char → string 시 string str = {c} 처럼 해주면 간편하다.

3. set<int>::iterator iter; for(iter=s.begin(); iter!=s.end(); iter++) cout << *iter ;

 

 

 

---