11067번: Monotone Walkway

https://www.acmicpc.net/problem/11067

x값이 다른 두 점에 대해서는 x값이 작은 점들의 번호가 작아야 한다. x가 같은 점들의 번호 순서는, 해당 x값보다 작으면서 가장 큰 번호의 점을 찾고 이 번호의 y값을 시작으로 오름차순 혹은 내림차순 정렬해서 매기면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int t, n, m, x;
pair<int, int> p[100001];
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
        sort(p + 1, p + 1 + n);
        for (int i = 1, e; i < n; i = e) {
            e = upper_bound(p + 1, p + 1 + n, make_pair(p[i].first, int(1e9))) - p;
            if (p[i].second^p[i - 1].second) reverse(p + i, p + e);
        }
        for (scanf("%d", &m); m--;) scanf("%d", &x), printf("%d %d\n", p[x].first, p[x].second);
    }
    return 0;
}

13264번: 접미사 배열 2

https://www.acmicpc.net/problem/13264

앞에서부터 1, 2, 4, ...개를 보며 계수 정렬하는 풀이
http://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<cstring>
char s[100001];
int r[100000], t[100000], sa[100000], c[100000], n, sz;
void csort() {
    for (int i = 0; i < sz; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[r[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i - 1];
    for (int i = n; i--;) sa[--c[r[t[i]]]] = t[i];
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    sz = 128 < n ? n : 128;
    for (int i = 0; i < n; i++) r[i] = s[i], t[i] = i;
    csort();
    for (int i = 1, k; i < n; i <<= 1) {
        k = 0;
        for (int j = n - i; j < n; j++) t[k++] = j;
        for (int j = 0; j < n; j++) if (sa[j] >= i) t[k++] = sa[j] - i;
        csort();
        k = 0;
        for (int j = 0; j < n; j++) t[sa[j]] = !j || sa[j] + i < n && sa[j - 1] + i < n &&r[sa[j]] == r[sa[j - 1]] && r[sa[j] + i] == r[sa[j - 1] + i] ? k : ++k;
        for (int j = 0; j < n; j++) r[j] = t[j];
    }
    for (int i = 0; i < n; i++) printf("%d\n", sa[i]);
    return 0;
}

1838번: 버블 정렬

https://www.acmicpc.net/problem/1838

$O(n\lg n)$

답은 각 수에 대해 정렬 후 앞으로 가게 되는 칸 수의 최댓값

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[500000];
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i].first), p[i].second = i;
    sort(p, p + n);
    for (int i = 0; i < n; i++) r = max(r, p[i].second - i);
    printf("%d", r);
    return 0;
}

1431번: 시리얼 번호

https://www.acmicpc.net/problem/1431


$O(nL\lg n)$

#include<iostream>
#include<string>
#include<tuple>
#include<algorithm>
using namespace std;
int n;
tuple<int, int, string> p[1000];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> get<2>(p[i]);
        for (char c : get<2>(p[i])) if (c <= '9') get<1>(p[i]) += c - '0';
        get<0>(p[i]) = get<2>(p[i]).size();
    }
    sort(p, p + n);
    for (int i = 0; i < n; i++) cout << get<2>(p[i]) << endl;
    return 0;
}

2800번: ZAGRADE

https://www.acmicpc.net/problem/2800


$O(ln2^n)$

stack으로 괄호쌍을 찾아준 다음, 비트마스크를 이용해 가능한 모든 문자열을 구하고 사전순 정렬한다.

#include<iostream>
#include<string>
#include<set>
using namespace std;
string s;
int cnt, stk[10], top;
pair<int, int> p[10];
set<string> st;
int main() {
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') p[stk[top++] = cnt++].first = i;
        if (s[i] == ')') p[stk[--top]].second = i;
    }
    for (int i = 1 << cnt; --i;) {
        int ck[200] = {};
        for (int j = 0; j < cnt; j++) if (i & 1 << j) ck[p[j].first] = ck[p[j].second] = 1;
        string r;
        for (int j = 0; j < s.size(); j++) if (!ck[j]) r += s[j];
        st.insert(r);
    }
    for (auto it : st) cout << it << endl;
    return 0;
}

1246번: 온라인 판매

https://www.acmicpc.net/problem/1246


$O(m\lg m)$

당연하게도 pi가 큰 사람부터 팔아야 한다.
<pi>를 내림차순 정렬했을 때
답은 pi*i가 가장 클 때 pi, pi*i

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int a[1001], n, m, r;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d", a + i);
    sort(a + 1, a + 1 + m, greater<int>());
    for (int i = 1; i <= m&&i <= n; i++) if (a[i] * i > a[r] * r) r = i;
    printf("%d %d", a[r], r*a[r]);
    return 0;
}

11656번: 접미사 배열

https://www.acmicpc.net/problem/11656


$O(l^2\lg l)$

사전순 정렬

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a, s[1000];
int main() {
    cin >> a;
    for (int i = 0; i < a.size(); i++) s[i] = a.substr(i);
    sort(s, s + a.size());
    for (int i = 0; i < a.size(); i++) cout << s[i] << endl;
    return 0;
}

11650번: 좌표 정렬하기

https://www.acmicpc.net/problem/11650


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[100000];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + n);
    for (int i = 0; i < n; i++) printf("%d %d\n", p[i].first, p[i].second);
    return 0;
}

11651번: 좌표 정렬하기 2

https://www.acmicpc.net/problem/11651


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[100000];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d%d", &p[i].second, &p[i].first);
    sort(p, p + n);
    for (int i = 0; i < n; i++) printf("%d %d\n", p[i].second, p[i].first);
    return 0;
}

10814번: 나이순 정렬

https://www.acmicpc.net/problem/10814


$O(n(\lg n+L))$

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n;
pair<int, int> p[100000];
string s[100000];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i].first >> s[i], p[i].second = i;
    sort(p, p + n);
    for (int i = 0; i < n; i++) cout << p[i].first << ' ' + s[p[i].second] << endl;
    return 0;
}

10989번: 수 정렬하기 3

https://www.acmicpc.net/problem/10989


$O(n)$

#include<cstdio>
int a[10001], n, x;
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), a[x]++;
    for (int i = 1; i <= 1e4; i++) while (a[i]--) printf("%d\n", i);
    return 0;
}

1764번: 듣보잡

https://www.acmicpc.net/problem/1764


$O(l(n+m)lg(n+m))$

사전순 정렬을 이용한다.

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s[1000000];
int n, m, r;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n + m; i++) cin >> s[i];
    sort(s, s + n + m);
    for (int i = 1; i < n + m; i++) r += s[i] == s[i - 1];
    cout << r << endl;
    for (int i = 1; i < n + m; i++) if (s[i] == s[i - 1]) cout << s[i] << endl;
    return 0;
}

1900번: 레슬러

https://www.acmicpc.net/problem/1900


$O(n\lg n)$

(힘,마술링 힘)이 주어졌을 때
(xi,yi)가 (xj,yj)를 이길 조건은 xi+yi*xj > xj+yj*xi
이 조건은 xi/(yi-1) < xj/(yj-1)일 조건과 동치이다.
(yi=1이면 해당 항이 무한대로 간다고 가정하자. 이러한 레슬러는 문제 조건에 따라 많아야 하나 존재한다.)
즉, xi/(yi-1) 값에 따라 모든 레슬러의 순위를 결정할 수 있으므로 그 순위와 반대로 동호와 만나게 하면 금화가 최소로 든다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct st {
    int x, y, idx;
}a[10001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].idx = i;
    }
    sort(a + 1, a + 1 + n, [](st i, st j) {return i.x + i.y*j.x > j.x + j.y*i.x; });
    for (int i = 1; i <= n; i++) printf("%d\n", a[i].idx);
    return 0;
}

2947번: 나무 조각

https://www.acmicpc.net/problem/2947


$O(1)$

버블 정렬을 구현한다.

#include<cstdio>
int a[5];
int main() {
    for (int i = 0; i<5; i++) scanf("%d", a + i);
    for (int i = 5; --i;) {
        for (int j = 0; j<i; j++) if (a[j]>a[j + 1]) {
            a[j] ^= a[j + 1] ^= a[j] ^= a[j + 1];
            for (int k = 0; k<5; k++) printf("%d ", a[k]);
            puts("");
        }
    }
    return 0;
}

10825번: 국영수

https://www.acmicpc.net/problem/10825


$O(nl\lg n )$

#include<iostream>
#include<algorithm>
#include<tuple>
#include<string>
using namespace std;
tuple<int, int, int, string> tp[100000];
int n;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> get<3>(tp[i]) >> get<0>(tp[i]) >> get<1>(tp[i]) >> get<2>(tp[i]),
        get<0>(tp[i]) *= -1, get<2>(tp[i]) *= -1;
    sort(tp, tp + n);
    for (int i = 0; i < n; i++) cout << get<3>(tp[i]) + '\n';
    return 0;
}

2385번: Secret Sharing

https://www.acmicpc.net/problem/2385


$O(n^2)$



먼저, 0으로 시작하면 안된다는 조건을 무시하고 생각해보자.

나열할 때, 대충 생각할 수 있는 방법으로는 사전순 정렬이 있다. 물론 이 방법에는 다음과 같은 반례가 존재한다.

345

34512

사전순 정렬 후 나열: 34534512

정해: 34512345


기본적으로 사전배열이 최적해를 도출해내는 것은 맞다.
모든 조각들 p, q 쌍에 대해 사전순 비교를 할 때 문자열의 끝에 도달하기 전에 순서가 결정된다면 (p,q)사전순 비교를 통해 답을 내놓아도 상관없다.
위의 예와 같이 공백문자열에 의해 순서가 뒤바뀌는 것이 문제이다.

공백문자열에 의해 순서가 뒤바뀔 수 있는 쌍들은 (p,q)사전식 비교를 통해 정렬했을 때 인접하게 된다는 것을 알 수 있다.
고로 서로 간의 우선순위만 따지면 되며(즉, p와 q사이에 어떤 문자열도 오지 않을 것이다.) 이것을 해결하기 위해 string p와 q를 비교할 때 p+q 와 q+p를 사전순 비교하면 된다.



0이 처음에 올 수 없다는 조건을 추가해도 위에서 쓰인 아이디어를 적용하면 어렵지 않게 해결된다.

0이 첫글자인 string을 위 비교함수로 정렬하여 나열한 문자열을 t라고 하자.

암호 키의 첫 번째에 오는 조각은 p+t+q와 q+t+p를 비교하여 사전순으로 가장 앞에 오는 p이다.

p 뒤에 나머지 문자열들을 정렬한대로 나열하면 된다.
아무거나 하나씩 제일 앞에 두고 나머지 조각들을 위와 같이 정렬해서 따져봐도 된다. 이 경우 시간복잡도는 $O(n^2lgn)$

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s[100], t;
bool cmp1(string i, string j) { return i + j<j + i; }
bool cmp2(string i, string j) { return i + t + j<j + t + i; }
int n, i;
int main() {
    cin >> n;
    for (i = 0; i<n; i++) cin >> s[i];
    sort(s, s + n, cmp1);
    for (i = 0; i<n && s[i][0] == '0'; i++) t += s[i];
    if (i == n) cout << "INVALID";
    else {
        int p = min_element(s + i, s + n, cmp2) - s;
        cout << s[p];
        for (int i = 0; i<n; i++) if (i^p) cout << s[i];
    }
    return 0;
}

1181번: 단어 정렬

https://www.acmicpc.net/problem/1181


$O(nl\lg n)$

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
string s[20000];
bool cmp(string i, string j) {
    return i.length() < j.length() || i.length() == j.length() && i < j;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n, cmp);
    n = unique(s, s + n) - s;
    for (int i = 0; i < n; i++) cout << s[i] << endl;
    return 0;
}

2751번: 수 정렬하기 2

https://www.acmicpc.net/problem/2751


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
int n, a[1000000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    std::sort(a, a + n);
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}

2750번: 수 정렬하기

https://www.acmicpc.net/problem/2750


$O(n\lg n)$

#include<cstdio>
#include<algorithm>
int n, a[1000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    std::sort(a, a + n);
    for (int i = 0; i < n; i++) printf("%d\n", a[i]);
    return 0;
}