백준 1251 단어 나누기

1. 아이디어는 어렵지 않으나, 구현에서 꼼꼼함이 요구됩니다. 2. 예를 들어서 회전시키는 것에서 인덱스가 헷갈립니다. 3. 인덱스를 포함했을 때 어디까지 변환을 할 것인가. 처음에 어떻게 들어갈 것인가. 0,1 차이이므로 조심스레 구현합니다. 그리고 명확하게 구현합니다. 여기서 많이 했던 실수는 인덱스도 많고 원본, 변경, 최소맵 3개를 번갈아가면서 사용해야 해서 시간이 10분정도 소요됬습니다. 설계가 완벽하므로, 처음에 설계를 하고 시간복잡도를 생각해보고 풀이를 시작해보도록 합니다.

/*
18:54 시작합니다.

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는
사전순으로 정리를 하려면 

1. 3등분 하는 함수 dfs
2. 뒤집는 함수
3. 사전순 비교하는 함수. (안에 들은 배열하나씩 비교하면 됩니다.)
*/
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
#define SIZE 52 // 52
 
int map[SIZE];
int map_store[SIZE];
int min_store[SIZE];
string str;
int len;
 
void problemIn() {
    cin >> str;
    len = str.size();
    for (int i = 0; i < len; i++) {
        map[i] = str[i];
        map_store[i] = map[i];
    }
    
    for (int i = 0; i < len; i++) {
        min_store[i] = 'z';
    }
}
 
/*
짝수 홀수로 나누어서 풀이합니다.
짝수라면 4자리 숫자라면,

일단 3 이랑, 4가 들어왔다고 가정 합니다.
1 2 3 4 /5/ 6 7 8

2가들어왔다고 가정합니다. 그럼
3이빈다.

4가 들어오면,

  i = 3 으로 고정을 두고, 고정을 두고 좌우로 변경하면 됩니다. 그런데 얼만큼을 변경할 것인지
*/
void turn(int x, int y) {
 
    if ((x % 2) == 1) { // 짝수개라면,
        int i = x / 2;
        for (int j = 0; j <= x / 2; j++) {
            swap(map[i - j], map[i + 1 +j]);
        }
    }
    if ((x % 2) == 0) { // 홀수개라면,
        int i = x / 2;
        for (int j = 1; j <= (x / 2); j++) {
            swap(map[i-j], map[i+j]);
        }
    }
 
    //가운데 회전시키기
    int a = y - x; // 4 입니다. 
    if (a % 2 == 0) {
        int i = x + (a / 2);
        for (int j = 0; j < a / 2; j++) {
            swap(map[i-j], map[i+j+1]);
        }
    }
    else {
        int i = x + (a / 2) + 1;
        for (int j = 1; j <= a / 2; j++) {
            swap(map[i-j], map[i+j]);
        }
    }
    
    //마지막 회전시키기
    int b = len - y - 1; // 2입니다. 지금
    if (b % 2 == 0) {
        int i = len - (b / 2) - 1;
        for (int j = 0; j < (b / 2); j++) {
            swap(map[i-j], map[i+j+1]);
        }
    }
    else {
        int i = len - (b / 2) - 1;
        for (int j = 1; j <= (b / 2); j++) {
            swap(map[i-j], map[i+j]);
        }
    }
}
 
/*
원본하나 저장
변경하는 맵 하나 저장
최고 하나 저장

*/
void solve() {
    
    for (int i = 0; i < len-1; i++) {
        for (int j = i + 1; j < (len-1); j++) {
            turn(i, j);
            
            // map check
            for (int k = 0; k < len; k++) {
                if (map[k] == min_store[k]) {
                    continue;
                }
                else if (map[k] < min_store[k]) {
                    for (int l = 0; l < len; l++) {
                        min_store[l] = map[l];
                    }
                    break;
                }
                else {
                    break;
                }
            }
            
            // map recovery
            for (int m = 0; m < len; m++) {
                map[m] = map_store[m];
            }
        }
    }
 
 
    for (int i = 0; i < len; i++) {
        cout << (char)min_store[i];
    }
    cout << endl;
}
 
int main() {
    problemIn();
    solve();
 
    return 0;
}