Koios1143的筆記

Kattis - Sideways Sorting

發表於 分類於

Kattis - Sideways Sorting

題目

https://open.kattis.com/problems/sidewayssorting

一般來說我們排序字串都是由左到右，但是本題要我們由上到下來看

輸入第一行包含兩個正整數 $r, c$，表示 row 與 column

接下來有 $r$ 行，每行 $c$ 個字元

最後輸出垂直方向由上到下的穩定排序

並且排序過程當中忽略大小寫

舉例來說

1
2
3
oTs
nwi
eox

從垂直的方向來看，我們會得到三個字串

1
2
3
one
Two
six

接下來排序這幾個字串

1
2
3
one
six
Two

最後排回原本的橫向

1
2
3
osT
niw
exo

想法

因為排序的方向是垂直的，我們可以直接以垂直的方式儲存這些字串即可

接下來穩定排序過後在改變輸出的方向即可

至於排序的部分，我們可以先把所有要比較的字串先都轉換成小寫之後再來比較大小

Code

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
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string arr[20];
bool cmp(string p, string q){
	// 先轉換成小寫 
	for(int i=0 ; i<p.size() ; i++){
		p[i] = tolower(p[i]);
	}
	for(int i=0 ; i<q.size() ; i++){
		q[i] = tolower(q[i]);
	}
	// 接下來再比較大小 
	if(p != q) return p<q;
	return false;
}
int main(){
	int r,c;
	char tmp;
	bool out=false;
	while(cin>>r>>c && (r!=0 && c!=0)){
		// 輸出之間需要有換行 
		if(out) cout<<"\n";
		else out=true;
		
		// 初始化所有字串 
		for(int i=0 ; i<c ; i++){
			arr[i] = "";
		}
		
		for(int i=0 ; i<r ; i++){
			for(int j=0 ; j<c ; j++){
				// 把字串串起來
				cin>>tmp;
				arr[j]+=tmp;
			}
		}
		
		stable_sort(arr, arr+c, cmp);
		
		for(int i=0 ; i<r ; i++){
			for(int j=0 ; j<c ; j++){
				// 記得輸出方向是相反
				cout<<arr[j][i];
			}
			cout<<"\n";
		}
	}

	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(rc)$

每筆測資初始化時間複雜度為 $O(rc)$

每筆測資排序時間複雜度為 $O((len(p) + len(q)) \times nlogn)$

每筆測資輸出時間複雜度為 $O(rc)$

每筆測資總時間複雜度約為 $O(rc + nlogn)$ ($len(p) + len(q)$ 很小，可以忽視)