POJ 1007
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 88227
Accepted: 35442
Description
One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.
Input
The first line contains two integers: a positive integer n (0 < n <= 50) giving the length of the strings; and a positive integer m (0 < m <= 100) giving the number of strings. These are followed by m lines, each containing a string of length n.
Output
Output the list of input strings, arranged from ``most sorted'' to ``least sorted''. Since two strings can be equally sorted, then output them according to the orginal order.
Sample Input
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
Sample Output
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
import java.util.Scanner;
public class Poj1007 {
private static DNA[] ret;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
ret = new DNA[m];
for (int i = 0; i < m; i++) {
DNA dna = new DNA();
dna.value = sc.next();
dna.sortNum = calSortNum(dna.value);
// ret[i] = dna;
addToArray(dna);
}
for (int i = 0; i < m; i++) {
System.out.println(ret[i].value);
}
}
//
private static int calSortNum(String str) {
if (str.length() == 1) {
return 0;
}
int sortF = 0;
char c = str.charAt(0);
for (int i = 1; i < str.length(); i++) {
if (c > str.charAt(i)) {
sortF++;
}
}
return sortF + calSortNum(str.substring(1));
}
//
private static void addToArray(DNA dna) {
for (int i = 0; i < ret.length; i++) {
if (ret[i] != null) {
if (dna.sortNum < ret[i].sortNum) {
//
for (int j = ret.length - 1; j > i; j--) {
ret[j] = ret[j - 1];
}
ret[i] = dna;
break;
}
} else {
ret[i] = dna;
break;
}
}
}
// DNA , , ,
private static class DNA {
String value;
int sortNum;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.