백준 6137 : 문자열 생성

6137번: 문자열 생성 (acmicpc.net)

6137번: 문자열 생성

설명

문자열의 양쪽에서 사전순으로 빠른 문자부터 하나씩 t에 삽입한다.

만약 우선순위가 같다면 사전순으로 빠른 문자가 먼저 오는 쪽부터 우선적으로 삽입한다.

 

본인은 같은게 나오면 빠른 문자가 오는 방향의 모든 문자를 한번에 미리 다 넣어봤는데 오류가 났다. 왜 틀렸는지 결국 해결하지 못하고 다른 풀이를 참고함

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

int main() {
    init();
    //문자열 입력받기
    int n; cin >> n;
    vector<char> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    //출력할 문자열
    string t;

    //좌우로 비교, 사전순으로 빠른 문자부터 삽입
    int low = 0;
    int top = n - 1;
    while (low <= top) {
        if (low == top) {
            t.push_back(v[low]);
            break;
        }
        if (v[low] < v[top]) {
            t.push_back(v[low++]);
        }
        else if(v[low]>v[top]){
            t.push_back(v[top--]);
        }
        else {
            int ll = low;
            int tt = top;
            while (ll<=tt && v[++ll] == v[--tt]);
            
            if (v[ll] < v[tt]) {
                t.push_back(v[low]);
                low++;
            }
            else {
                t.push_back(v[top]);
                top--;
            }
        }
    }
    int cnt = 0;
    for (const char& c : t) {
        cout << c;
        if (++cnt == 80) {
            cout << endl;
            cnt = 0;
        }
    }
}