문제 이해 단계
입력으로 테스트케이스 T와 알파벳(문자열)이 주어지면,
그 알파벳들을 사전순으로 배열한다고 가정한다.
사전순으로 쭉 나열했을 때,
입력으로 들어온 문자열 다음으로, 나올 문자열을 출력하는 것이 해당 문제
문제 접근 단계
해당 문제에서는 동일한 문자열에 있는 알파벳들 간의 사전순,
즉 아스키코드의 크기가 중요하다.예제 입력으로 나와있는 것으로 한번 보자.
알기 쉽게 문자 말고 사전순서의 순위로 표시해 보자.
HELLO → HELOL == 21334 → 21343
DRINK → DRKIN == 15243 → 15324
SHUTTLE → SLEHTTU == 5264431 →5312446
ZOO → ZOO == 211 → 211
노란색 바탕인 숫자들은 변화가 일어난 부분들이다.
해당 영역에서 위치이동이 일어났다.
이제 이를 보면서 노란색 영역이 결정지어지는 조건, 영역 안에서 문자가 나열되는 로직을 생각해 보자.
노란색 영역 결정 조건
노란색 영역, 즉 위치 이동이 일어나는 영역은 어떻게 결정할 수 있을까?
위에서 그린 그림들을 보면 모두 공통점이 있다.
노란색 영역에 가장 앞에 있는 수를 제외하곤
모두 내림차순 정렬되어 있다.
21334 → 21343
15243 → 15324
5264431 →5312446
정렬 전의 상태에서 노란색 영역의 가장 앞에 부분을 제외하고 생각했을 때,
나머지 수들은 모두 내림차순으로 정렬되어 있는 것을 확인할 수 있다.
이 점을 통해 노란색 영역의 시작점은
내림차순이 끊기는 알파벳을 포함하는 시점이라는 것을 알 수 있다.
즉, 마지막 인덱스부터 탐색했을 때,
i번 인덱스가 i+1 인덱스보다 작다면 그 위치가 교환의 시작점이라는 것이다.
왜 첫 인덱스가 아닌 마지막 인덱스부터 탐색을 할까?
HELLO 예시를 보자.
21334 → 21343
이걸 만약 첫 인덱스부터 탐색하여 i번째 인덱스가 i+1번째 인덱스보다 작을 때를 찾으면?
21334
의도했던 노란색 사각형 영역이 전혀 다르게 나온다.
그래서 의도한 대로 나오기 위해서는 마지막 인덱스부터 역탐색해야 한다.
문자가 나열되는 로직
노란색 영역 밖에 있는 문자는 위치가 변하지 않기 때문에
안에 있는 알파벳만 살펴보자.
34 → 43
243 → 324
264431 →312446
가장 앞에 있는 숫자(알파벳)가
다른 위치에 있는 알파벳과 교환된다.
어떤 원리로 교환되는 것일까?
일단 해당 문제는 사전순으로 나열하는데,
주어진 문자열 다음에 나타날 문자열을 출력하는 것이다.
알파벳이 주어졌을 때, 사전순으로 가장 처음 나타나는 문자열은 무엇일까?
당연히 문자열에 있는 알파벳들을 오름차순 정렬했을 때이다.
사전순으로 빠른 숫자를 앞으로 할수록 유리하기 때문그렇다면 가장 끝에 오는 것은?
내림차순 정렬되어 있는 것이다.
사전순으로 느린 것을 최대한 앞으로 몰았기 때문이다.
이 원리를 문자가 나열되는 로직에 적용하였다.
노란색 영역이 결정되는 조건이 내림차순이 끊기는 순간이라고 했다.
이 말은 가장 앞에 있는 수를 제외하고 뒤에 있는 수들은 전부 내림차순 정렬되어 있단 소리다.
또한 내림차순 되어있는 문자들로만 이루어진 알파벳들 안에서는
그 문자 배열이 가장 마지막에 오는 것이다.
그 앞에 내림차순을 끊는 수가 오는 것일 뿐.
위 그림을 보면 어느 정도 이해가 될 것이다.
다른 말로는 이렇게도 해석할 수 있다.
2가 가장 앞에 있을 때 만들 수 있는 배열 중 사전 순으로 가장 느린 배열
즉, 이다음 문자열은 맨 앞이 2가 아니라는 소리이다.
그럼 뭐가 와야 할까?
사전순서이기 때문에 2 다음으로 작은 3이 와야 할 것이다.
그리고 그 뒤에 있는 수 배열들은 오름차순 정렬되어야 한다.
왜? 3이 가장 앞에 있을 때 만들 수 있는 배열 중에 가장 작은 것을 만들어야 하기 때문이다.
이제 여기에 노란색 영역 밖에 있었던 5만 붙이면
우리가 구하고자 했던 5264431 다음에 오는 배열임을 확인할 수 있다.
이를 좀 더 단계적으로 정리해 보면 이렇다.
1. 노란색 영역 가장 앞에 있는 숫자(알파벳)를 제외하고
그 뒤에 있는 숫자들만 본다.
2. 노란색 영역 가장 앞에 있는 숫자보다 큰 수 중
사전순으로 가장 앞선 것(가장 숫자가 낮은 것)을 선택한다.
3. 노란색 영역 가장 앞 숫자와 선택한 숫자를 교환한다.
4. 맨 앞자리 수를 제외한 뒤에 있는 나머지 숫자를
오름차순 정렬한다.
노란색 영역을 지정하는 방법과 그 지정한 영역에서 배열하는 방법을 이용하면 답을 구할 수 있다.
이것이 첫 번째 방법이다.
두 번째 방법은 헤더파일 <algorithm>에 있는 permutation(순회)를 사용한 풀이이다.
이 방식은 짧기 때문에 문제 구현 단계에서 바로 보여주겠다.
문제 구현 단계
첫 번째 방법
// 노란색 영역 안에 문자를 배열하는 함수
// size : 배열 크기, idx : 노란색 영역 가장 앞에 있는 수 인덱스
void findNextWord(char word[], int size, int idx){
// 문자가 2개라면
if(size <= 2) {
// 그냥 뒤집고 끝냄
reverse(word,word+size);
cout << word << "\n";
return;
}
// 맨 앞 문자 바꾸기
char key = word[idx];
int changeWord = 9999; // 작은 수가 출력되기 위함
int select = idx; // 선택된 위치 인덱스
for(int i = idx+1; i < size; i++){
// 노란색 영역 맨 앞에 수와 같거나 작은 경우 제외
if(word[i] <= key) continue;
// 가장 작은 수를 선택
if(word[i] < changeWord){
changeWord = word[i];
select = i;
}
}
// 두 수를 교환
word[idx] = word[select];
word[select] = key;
// 맨 앞을 제외하고 오름차순
sort(word+idx+1,word+size);
// 출력
for(int i = 0; i < size; i++) printf("%c",word[i]);
printf("\n");
}노란색 영역 안에서 문자를 배열하는 함수이다.
size를 통해 문자열 길이를 입력받는데,
이는 인자로 배열을 넘기기 때문에 길이를 그냥 넘겨주는 게 편하다.
string을 사용하지 않는 것은, string을 사용함으로써
발생하는 메모리 낭비 문제를 막기 위해서이다.
실제로 해당 함수를 string으로 작성했는데 메모리초과가 떠서 못 풀었다..
문자열의 길이가 2 이하라면 단순 교환만 해주면 되기 때문에 문자열 자체를 뒤집어준다.
3 이상을 경우 위에서 말했던 배열을 시작한다.
코드 자체는 간단하기 때문에 알아보기 어려운 것은 없을 것이다.
int main(){
int T;
cin >> T;
while(T--){
string word; // 입력받은 단어
cin >> word;
bool isChange = false; // 수정됐는지 체크
int size = word.size();
char arr[size];
for(int i = 0; i < size; i++) arr[i] = word[i];
// 끝 인덱스부터 역탐색
for(int i = size-2; i >= 0; i--){
// 내림차순을 끊는 인덱스를 찾으면 해당 인덱스에서
// findNextWord 알고리즘 시작
if(word[i] < word[i+1]){
isChange = true;
findNextWord(arr,size,i);
break;
}
}
// 값 수정이 없었다면, 문자 그대로 출력
if(!isChange) cout << word << "\n";
}
}입력을 받는 방법에 대해 서술해 놨다.string으로 입력받아 그 길이를 가져와서
그 길이에 해당하는 배열을 만들어서 넣는다.
그 아래부터는 노란색 영역을 찾는 부분이다.
내림차순이 끊기는 인덱스 위치에서 findNextWord 함수를 실행한다.
그리고 여기에는 isChange라는 bool 형 변수를 뒀는데,
이는 ZOO같이 아예 변경이 필요 없을 경우를 위해서이다.
이 경우, findNextWord 함수가 실행되지 않기 때문에 그런 경우 word 자체를 실행시키기 위함이다.
아래 전체 코드를 올리겠다.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
// 노란색 영역 안에 문자를 배열하는 함수
// size : 배열 크기, idx : 노란색 영역 가장 앞에 있는 수 인덱스
void findNextWord(char word[], int size, int idx){
// 문자가 2개라면
if(size <= 2) {
// 그냥 뒤집고 끝냄
reverse(word,word+size);
cout << word << "\n";
return;
}
// 맨 앞 문자 바꾸기
char key = word[idx];
int changeWord = 9999; // 작은 수가 출력되기 위함
int select = idx; // 선택된 위치 인덱스
for(int i = idx+1; i < size; i++){
// 노란색 영역 맨 앞에 수와 같거나 작은 경우 제외
if(word[i] <= key) continue;
// 가장 작은 수를 선택
if(word[i] < changeWord){
changeWord = word[i];
select = i;
}
}
// 두 수를 교환
word[idx] = word[select];
word[select] = key;
// 맨 앞을 제외하고 오름차순
sort(word+idx+1,word+size);
// 출력
for(int i = 0; i < size; i++) printf("%c",word[i]);
printf("\n");
}
int main(){
int T;
cin >> T;
while(T--){
string word; // 입력받은 단어
cin >> word;
bool isChange = false; // 수정됐는지 체크
int size = word.size();
char arr[size];
for(int i = 0; i < size; i++) arr[i] = word[i];
// 끝 인덱스부터 역탐색
for(int i = size-2; i >= 0; i--){
// 내림차순을 끊는 인덱스를 찾으면 해당 인덱스에서
// findNextWord 알고리즘 시작
if(word[i] < word[i+1]){
isChange = true;
findNextWord(arr,size,i);
break;
}
}
// 값 수정이 없었다면, 문자 그대로 출력
if(!isChange) cout << word << "\n";
}
}이 것이 첫 번째 방법에 대한 설명이고 두 번째 방법에 대한 설명을 하겠다.
두 번째 방법
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
string word;
cin >> word;
// 다음 순열이 없다면 이전 순열로 돌아옴
if(!next_permutation(word.begin(),word.end())){
prev_permutation(word.begin(),word.end());
}
for(auto it : word) cout << it;
cout << "\n";
}
}상당히, 아니 그냥 짧다.
이 문제를 위해 존재하는 함수같이 너무 딱 들어맞는다.
next_permutation() 함수는 현재 값을 하나하나의 순열로 배치할 때,
넣었던 문자열의 다음 순열을 출력하는 것이다.
이는 사전순으로 되기 때문에 자동으로 넣었던 word의 다음 순열인 답이 나오게 되는 것이다..
조건문은 그냥 마지막 문자임을 체크..
prev는 다음 순열이 아닌 이전 순열을 뜻하는 완전히 같은 함수
...
시행착오
이 문제를 풀 때 진짜 고생했다.
메모리 초과, 시간 초과, 컴파일 에러 등등 볼 수 있는 에러는 다 본 것 같다.
문제를 해석하는 것도 어려웠고, 로직을 세우는 것도 나름 어려웠다.
제일 어려웠던 것은 메모리초과를 해결하는 문제.
덕분에 string이 메모리를 엄청나게 잡아먹어서 string을 자주 출력해야 할 때는
웬만하면 배열을 사용하자라고 느꼈다.
근데 permutation 진짜 열받네