소트 게임

작성일 | In

[백준] 1327번 - 소트 게임

문제 링크

오랜만에 문자열 관련 문제를 접해서인지 몰라도 풀어내는데 꽤 난항을 겪었다.
주어진 수열의 부분 수열을 역순으로 뒤집어가면서 이 수열을 오름차순으로 정렬할 수 있는지를 묻는 문제이다.
처음에는 버블 소트를 응용해서 풀어야 하는줄 알았는데, 제시된 수열의 크기(n)가 2 이상 8이하로 굉장히 작았기에 브루트포스 알고리즘일 것이라 짐작했다.

모든 경우의 수를 탐색해봐야 하기 때문에, 공간복잡도를 생각해서 수열을 int 배열에 저장하지 않고 문자열화하여 탐색했다.
또한 낮은 시간복잡도를 위해, 수열의 상태를 중복해서 탐색하지 않기 위한 방문 기록을 저장하는 자료구조로 c++ STL 중 set를 선택했다.
set 자료구조는 이진 트리를 기반으로 중복되지 않는 key를 저장하는 STL이다. 이진 트리 기반이고 삽입 시 정렬을 지원하므로 삽입, 탐색 시간이 O(logN)이다.
가능한 모든 수열의 상태는 9x8x7…x2x1 = 약 36만이므로 시간초과는 발생하지 않을 것으로 예상했다.

부분 수열을 역순으로 뒤집는 방법은 string.substr() 메서드를 이용했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

set<string> visited;
queue<pair<string, int>> que;
int n, k;

bool isAsc(string& seq) {
    for(int i=1; i<=n; ++i) {
        if(seq[i-1]-'0' != i)
            return false;
    }
    return true;
}

string reverseSeq(string seq, int idx) {
    string newSeq;
    string front = idx == 0 ? "" : seq.substr(0, idx);
    string sub = seq.substr(idx, k);
    string back = k+idx-1 == n ? "" : seq.substr(idx+k);
    reverse(sub.begin(), sub.end());
    newSeq.append(front).append(sub).append(back);
    return newSeq;
}

void bfs(string& start) {
    visited.insert(start);
    que.push({start, 0});
    while(!que.empty()) {
        string seq = que.front().first;
        int cnt = que.front().second;
        que.pop();

        if(isAsc(seq)) {
            printf("%d", cnt);
            return;
        }

        for(int i=0; i<n; ++i) {
            if(i + k <= n) {
                string next = reverseSeq(seq, i);
                if(visited.find(next) != visited.end())
                    continue;

                visited.insert(next);
                que.push({next, cnt+1});
            }
        }
    }
    printf("-1");
}

int main(void) {
    scanf("%d %d", &n, &k);
    string seq;
    for(int i=0; i<n; ++i) {
        int num;
        scanf("%d", &num);
        seq.append(to_string(num));
    }
    bfs(seq);
}
0%