SWEA 5672 / 올해의 조련사

입력받은 앵무새 이름을 순서대로 배열에 담고

시작(0) 끝(n-1)부터 아스키코드값을 비교한다.

시작이 작다면 시작을 새로운 배열에 넣고, 시작++

끝이 작다면 끝을 새로운 배열에 넣고, 끝--

그러나 문제는 시작과 끝이 같은 경우.

시작과 끝이 같다면 while문을 사용하여

first = 시작+1, second = 끝-1로 선언하고

first와 second의 값을 비교한다.

여기서 또 first와 second가 같다면 first++; second--;

하나씩 더할때 가장 중요한 것이 first의 값이 second의 값보다 커지면 안된다.

first와 second가 다를 때 까지 수행한 후, 

first의 아스키코드 값이 작다면 시작를 새로운 배열에 넣고, 시작++;

second의 아스키코드 값이 작다면 끝을 새로운 배열에 넣고, 끝--;

여기서 중요한 것이 시작과 끝의 값을 바로바로 1씩 더해주는 것이 아니라 

다른 변수에 저장한다음 다음 while로 넘어갈때 시작과 끝을 바꾸어주어야한다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
vector<char>arr;
vector<char>narr;
 
void makeNewline(int n) {
 
    int start = 0;
    int end = n - 1;
 
    if (start == n - 1) {
        narr.push_back(arr[start]);
    }
 
    while (start != end) {
        int nstart, nend;
        nstart = start;
        nend = end;
 
        if (int(arr[start]) < int(arr[end])) {  // 앞이 작을때
            narr.push_back(arr[start]);
            nstart++;
        }
        if (int(arr[start]) > int(arr[end])) {  // 뒤가 작을때
            narr.push_back(arr[end]);
            nend--;
        }
        if (int(arr[start]) == int(arr[end])) {
            int first = start + 1;
            int second = end - 1;
            bool same = false;
            bool diff = false;
 
            while (1) {
                if (arr[first] != arr[second]) {    
                    diff = true;
                    break;
                }
                else {
                    if (first + 1 <= second - 1) {
                        first++;
                        second--;
                    }
                    else {
                        same = true;
                        break;
                    }
                }
            }
 
            if (same == false) {
                if (int(arr[first]) < int(arr[second])) {
                    narr.push_back(arr[start]);
                    nstart++;
                }
                else {
                    narr.push_back(arr[end]);
                    nend--;
                }
            }
            if (same == true) {
                narr.push_back(arr[start]);
                nstart++;        
            }
        }
 
        start = nstart;
        end = nend;
        
        if (start == end) {
            narr.push_back(arr[start]);
        }
    }
    return;
}
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
    int a = 1;
    
    while (testcase--) {
        arr.clear();
        narr.clear();
 
        int n;
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            char tmp;
            cin >> tmp;
            arr.push_back(tmp);
        }
 
        makeNewline(n);
 
        cout << "#" << a << " ";
 
        for (int i = 0; i < narr.size(); i++) {
            cout << narr[i];
        }
        cout << endl;
        
        a++;
    }
}