문제 이해 단계
문제가 이해하기가 어려웠는데 최대한 쉽게 풀어써보겠다.
전체 문자열이 존재하고 하나씩 드러나게 하는데
이걸 전체 단어로 볼 때 사전순으로 가장 빠르게 하는 것이다.
앞에 있는 알파벳이 높을수록 사전순으로 빠르기 때문에
맨 앞부터 높은 알파벳부터 채우는 것이다.
예제 출력 3번을 보면 어느 정도 이해가 된다.
문제 접근 단계
해당 문제에서 포인트가 되는 부분은 총 2가지이다.
1. 다음에 올 문자를 정하는 규칙
2. 그 문자를 적절한 곳에 위치시키는 방법
1번은 문제 조건에서 사전 순으로 빠르게 선택하라고 했기 때문에
빠른 순서대로 선택해야 하기 때문에 중요한 것이고,
2번은 문자가 무조건 뒤에 추가되는 것이 아닌, 사이사이에 들어갈 수도 있기 때문이다.
예를 들어 AIK 다음에 AINK 이런 식으로 N이 끝이 아닌 K 전에 들어가고
ARTLINK 다음에 SARTKINK 이런 식으로 S가 맨 앞에 나온다.
이렇게 위치되는 기준과 법칙을 잘 설정해줘야 한다.
1. 다음에 올 문자를 정하는 규칙
위 방법은 그렇게 어렵지 않다.
문자형은 유니코드로 정수형으로 변환되어
크기 비교가 가능하기 때문에 단순비교만 해주면 된다.
문제가 되는 점은 범위를 어떻게 설정해 주냐는 건데,
단어 자체가 사전 순으로 높으려면 앞자리가 높을수록 사전순으로 더 크다.
예를 들어 BFFFF는 CAAAA보다 사전순으로 무조건 앞서는 것처럼 말이다.
그래서 다음에 올 알파벳을 뽑을 때,
현재 가지고 있는 것 중 사전 순으로 높은 알파벳을 뽑는다.
그리고 그 앞에 있는 알파벳들은 뽑은 알파벳이
가장 앞으로 오게 하기 위해 사용 순서가 밀린다.
그다음에 올 문자는 뽑은 알파벳 뒤에 있는 문자에서 정해야 한다.
어떻게 정해야 할까? 방법은 위와 같다.
그 그룹에서 가장 사전순을 빠른 알파벳을 고르면 된다.
그리고 그 알파벳 뒤에 있는 알파벳들로 반복... 이를 그림으로 나타나보면 아래와 같다.
각각의 사각형은 탐색 범위이다.
저 알파벳 중 가장 사전순으로 빠른 게 빨간색 알파벳이란 뜻이다.
이런 식으로 끝까지 탐색을 하고, 다음에는 어떤 알파벳이 오는 것이 사전순을 유지하는 게 이득일까?
그렇다 이득이 맞다. 지금까지 뽑을 수 있는 빠른 수들을 다 뽑았다.
그렇기 때문에 더 이상 최적의 문자는 존재하지 않기 때문에 앞자리에 영향이 덜 가는 방향으로 가야 한다.
왜냐하면 앞자리가 빠를수록 빠르단 말은,
반대로 앞자리가 느릴수록 사전 뒤 순으로 밀린다는 것을 뜻하기 때문이다.
예를 들어 BCAD란 수가 있고 현재 BA까지 드러난 상태라고 해보자.
이때 C를 드러낸 BCA가 빠를까? 아니면 D를 드러낸 BAD가 빠를까?
당연히 A가 더 앞에 있는 BAD가 더 빠를 것이다.
이렇듯 최대한 뒤 알파벳부터 채우되, 만약 위치가 같다면 이것도 문자순이 빠른 것이 더 낫다.
이렇게 절차적인 관점에서 한번 봤는데, 아직 로직적으로는 감이 안 온다.
그래서 이를 좀 더 다르게 살펴봤다.
STARTLINK에서 가장 빠른 알파벳 A를 정했을 때,
그다음에 사용할 알파벳은 알파벳 A 뒤에 있는 문자열들 중에서 정한다.
그러면 알파벳 A 앞에 있는 문자열들은 사용하지 않는 것일까? 그렇지 않다.
결국에는 모든 문자열을 출력해야 하기 때문이다.
우선순위만 뒤보다 밀릴 뿐이지, 앞에도 문자의 우선순위가 존재할 것이다.
그리고 이는 위에서 얘기했던 절차와 완벽히 일치할 것이다.
여기서 드는 생각이, 어떤 기준을 잡고 그 점을 중심으로 분할하여 작업하고
또 그 안에서 중심을 잡고 분할하여 작업하고..
결국 그 결과가 전체의 결과가 되는 것과, 계산의 순서가 중요하다는 점이
재귀함수를 이용하여 풀어야 된다는 것을 알았다.
그림으로 나타내면 아래와 같이 될 것이다.
해당 순서대로 재귀함수가 실행될 것이다.
이게 잘 이해가 안 될 수도 있는데,
어차피 문제 구현 단계에서 코드로 설명할 것이기 때문에 거기서 자세히 다루겠다.
2. 문자를 적절한 위치에 위치시키는 방법
문자들의 순서를 정하는 법은 알겠는데, 이걸 적절한 위치에 두는 방법을 찾는 게 어려웠다.
어떤 수는 맨 앞에 오고 , 어떤 수는 맨 뒤에 오고, 어떤 수는 사이에 오고 해서..
그래서 찾아낸 방법이 각 문자열의 인덱스들을 고정시켜 두고
bool 형으로 체크하여 켜져 있는 경우에만 출력하는 것으로 했다.
이게 무슨 말이냐면 각각의 문자를 스위치처럼 만들어,
일단은 모두 꺼져있는 상태로 초기화하고
해당 문자가 선택되면 스위치를 눌러 켜서 출력했을 때 출력되도록 하였다는 것이다.
이 역시 문제 구현 단계에서 코드를 통해 설명하겠다.
문제 구현 단계
pair<char,bool> str[100]; // 문자 최대 개수
//문자 출력 함수
void printWord(string word){
for(int i = 0; i < word.length(); i++){
// 켜져있는 것만 출력
if(str[i].second) cout << str[i].first;
}
cout << '\n';
}
// 재귀함수
void solution(int start, int end, string word){
// 최소 인덱스를 첫 값으로
int minIdx = start;
// 최소값 인덱스 찾기
for(int i = start; i <= end; i++)
if(str[minIdx].first > str[i].first) minIdx = i;
// 스위치 온
str[minIdx].second = true;
printWord(word);
//최소값 뒤에 있는 문자열
if(minIdx + 1 <= end) solution(minIdx+1,end,word);
//최소값 앞에 있는 문자열
if(minIdx - 1 >= start) solution(start,minIdx-1,word);
}코드 자체는 그렇게 길지 않다.
일단 pair를 이용하여 bool과 문자 하나를 뜻하는 char을 묶어주었다.
bool이 true일 때 켜진 것으로 간주하여 출력한다.
solution부분이 재귀함수 부분인데, 인자로 시작과 끝 탐색 범위를 받아 탐색범위를 제한한다.
마지막 word는 printWord에 넘겨주기 위해서 받아준 것뿐이다.
solution에서 하는 일은 간단히 현재 범위에서 사전순으로 가장 빠른 알파벳을 찾은 후,
그 값을 기준으로 앞에 있는 문자열과 뒤에 있는 문자열로 나눈다.
그리고 각각의 문자열에 대해 똑같은 solution을 수행하여 준다.
printWord는 그냥 bool형이 true인 것만 출력시켜 주는 함수이다.
설명은 이게 끝이고 아래에서 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <string>
using namespace std;
pair<char,bool> str[100]; // 문자 최대 개수
//문자 출력 함수
void printWord(string word){
for(int i = 0; i < word.length(); i++){
// 켜져있는 것만 출력
if(str[i].second) cout << str[i].first;
}
cout << '\n';
}
// 재귀함수
void solution(int start, int end, string word){
// 최소 인덱스를 첫 값으로
int minIdx = start;
// 최소값 인덱스 찾기
for(int i = start; i <= end; i++)
if(str[minIdx].first > str[i].first) minIdx = i;
// 스위치 온
str[minIdx].second = true;
printWord(word);
//최소값 뒤에 있는 문자열
if(minIdx + 1 <= end) solution(minIdx+1,end,word);
//최소값 앞에 있는 문자열
if(minIdx - 1 >= start) solution(start,minIdx-1,word);
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
string input;
cin >> input;
for(int i = 0; i < input.length(); i++)
str[i] = make_pair(input[i],false);
solution(0,input.length()-1,input);
return 0;
}
시행착오
푸는데 엄청 오래 걸렸다.
한없이 어렵게 생각하니까 어렵게만 느껴진다.
막상 푸니까 코드는 그렇게 복잡한 것 같지도 않고,
로직도 그렇게 복잡한 거 같지도 않은데, 풀 때는 뭐가 그렇게 어려웠는지 모르겠다.
구현 문제를 많이 안 풀어본 내 잘못이다.
구현 문제를 많이 풀어봐야겠다는 것을 다시 한번 느낀다.
꼭 다시 풀어보자. 많이 모자라다.
이걸 하루동안 풀었다는 게 자괴감이 든다.