[BOJ] 11656번 : 접미사 배열

1. problem : 

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

 

2. solution 1: 

#include <bits/stdc++.h>
using namespace std;
string s; 
vector<string> prefix; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s; 
	for (int i = 0; i < s.size(); i++) {
		string temp(s.begin() + i, s.end());
		prefix.push_back(temp);
	}
	sort(prefix.begin(), prefix.end(), [](string& a, string& b) {
		int idx = 0; 
		while (idx < prefix.size()) {
			if (a[idx] == b[idx]) idx++;
			else return a[idx] < b[idx];
		}
		return a[idx] < b[idx];
		});
	
	for (int i = 0; i < prefix.size(); i++) cout << prefix[i] << '\n';

}

prefix라는 배열을 만들어, 접미사들을 추가했다. 정렬은 sort()를 이용했고 , 비교연산자는 lambda함수로 작성했다. 

 

3. solution 2 : 

// Authored by : std-freejia
// Co-authored by : -
//http://boj.kr/21378a10916b42d19dce4bc7c841a73c
#include <bits/stdc++.h>
using namespace std;

string st;
vector<string> v;

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

  cin >> st;
  int stringlen = st.length();
  for(int i = 0; i < stringlen; i++) {
    string temp = st.substr(i);
    v.push_back(temp);
  }
  sort(v.begin(), v.end());
  for(auto i : v) cout << i << '\n';
  return 0;
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0F/solutions/11656.cpp

basic-algo-lecture/0x0F/solutions/11656.cpp at master · encrypted-def/basic-algo-lecture

이 풀이는 훨씬 더 간단했다. sort도 사실 cmp가 필요없이, default sort로 가능했다. 또한, substr() method를 알게되었다.