https://www.acmicpc.net/problem/9081
9081번: 단어 맞추기
입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알
www.acmicpc.net
문자열이지만 순열에 더 가까운 문제입니다.
주어진 단어의 사전 순으로 바로 다음 단어를 출력하는 문제로, next_permutation을 이용하였습니다.
next_permutation으로 다음 순열을 구하고, 출력하면 됩니다.
만약 마지막 단어라서 다음 순열을 구하지 못하더라도 주어진 단어를 유지하므로 그냥 출력해줍니다.
c++ 내장의 next_permutation을 사용하면 됐지만 직접 구현해보았습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <string>
using namespace std;
string str;
int N;
bool nextPermutation() {
int i = N - 1;
while (i > 0 && str[i - 1] >= str[i]) {
i--;
}
if (!i) return false;
int j = N - 1;
while (str[i - 1] >= str[j]) j--;
swap(str[i - 1], str[j]);
int k = N - 1;
while (i < k) swap(str[i++], str[k--]);
return true;
}
void func() {
nextPermutation();
cout << str << '\n';
}
void input() {
cin >> str;
N = str.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
'algorithm > String' 카테고리의 다른 글
| boj 10096 세 친구 (0) | 2021.01.29 |
|---|
