백준 - 13417

문제링크

문제요약

알파벳이 담겨있는 문제열을 두가지 방법에 따라 배치해 사전순으로 가장 빠른순으로 정렬하는 문제이다.

방법

1. 카드를 가장 오른쪽에 놓는다.
2. 카드를 가장 왼쪽에 놓는다.

풀이

그리디로 해결하는 문제이다.

 

그리디는 '명제'를 만들고 그 명제가 타당한지 확인하는 과정이 중요하다.

 

명제
현재 문자열과 새로 추가할 카드의 비교:

• 새로 추가할 카드가 현재 문자열의 첫 번째 문자보다 사전순으로 앞서면 왼쪽에 추가한다.
• 그렇지 않으면 오른쪽에 추가한다.

그리디 선택의 정당성

• 문자열을 점진적으로 만들 때, 각 단계에서 사전순으로 가장 작은 선택을 하면 최종 결과도 사전순으로 가장 앞서는 문자열이 된다.
• 이전 선택이 현재 선택에 영향을 주지 않으므로, 그리디 방법이 올바르게 작동한다.

---

소스코드

#include <iostream>
#include <vector>
using namespace std;

/*
A S D F G
abcdefghijklmnopqrstuvwxyz
맨오른쪽과 왼쪽을 비교해 작은애를 놓는다
*/
char arr[1005];
int t, n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;
        vector<char> v;
        for (int j = 0; j < n; j++) {
            cin >> arr[j];
            if (!v.size())
                v.push_back(arr[j]);
            else if (arr[j] <= v[0])
                v.insert(v.begin(), arr[j]);
            else
                v.push_back(arr[j]);
        }
        for (const char c : v) {
            cout << c;
        }
        cout << "\n";
    }
}