'algospot'에 해당되는 글 2건

예제 출력

A
HloolelWrd

어렵지 않게 풀어낼 수 있는 문제입니다. 문제에 나와 있는 대로 생각하여 풀 수도 있으나 좀 더 간소화 할 수 있는 방법으로 풀어봤습니다.

문자열을 받아서 짝수 인덱스를 출력하고, 홀수 인덱스를 출력하면 올바른 출력이 나옵니다.

문자열은 문자열 마지막에 '\0'이 입력됨으로 써 문자열의 끝을 알 수 있습니다. 따라서 주의해야 할 점은 문자열의 최대 길이가 100인 경우 101 자리에 '\0' 을 가져야 하므로 명시된 최대 길이 + 1 이상으로 잡아 두셔야 올바른 코딩이 가능합니다.

대체적으로 비슷한 형태 였으나 독특한 소스가 있어 한번 살펴보았습니다.#include<stdio.h> main() { int T,i; char s[256],*e,*o; for(scanf("%d\n",&T);T--;) { gets(s); e=s+128; o=e+64; for(i=0;s[i];i++) { ((i&1)?*(o++):*(e++))=s[i]; } *e=*o=0; printf("%s%s\n",s+128,s+192); } }

256 크기의 배열을 하나 만든 다음 포인터 char 형 변수 e, o 를 만들어 짝수와 홀수의 문자를 출력하기 위한 위치를 잡아뒀네요.

짝수의 이진수는 첫 자리가 0 이고 홀수는 1 인 것에 감안해서 i & 1 로 짝수와 홀수를 구분하였습니다. 그렇게 해서 짝수와 홀수를 구분하여 문자열을 집어 넣고 최종적으로 출력을 하였습니다.

예제 출력

abacbacb
aababbccdcdd
babababybybyeeeeegeggege
oh

abbaaccb → ab ba ac cb → ab < ac < ba < cb → abacbacb

2자리 씩 나눠서 앞자리 순으로 정렬 후 같은 알파벳 끼리 뒷자리를 기준으로 정렬합니다. 저는 가장 간단하고 많은 분들이 생각 해보셨을 것 같은 버블정렬을 이용하여 문제를 풀었습니다. 먼저 앞자리 알파벳으로 버블정렬 수행 후, 같은 자리 끼리 뒷자리 알파벳을 비교하여 정렬을 수행 했습니다.

가장 빠른 처리속도 분들의 소스를 봐보니 기수정렬을 이용해서 풀었더군요. 버블정렬보다 훨씬 간단하고 빨라 보입니다. 

혹시 기수정렬에 대해 모르시는 분들을 위해 간단하게 말씀드리고 자세한 내용은 따로 올리도록 할게요.

다른 분들의 소스 중 하나를 살펴볼게요.

#include<stdio.h> #include<string.h> char t[1000]; void rxSort(char s[]){ int n=0,i, d,c, cnt[32]; for(d=1;d>-1;d--){ for(i=0;i<32;i++){ cnt[i]=0; } i=0; while(s[2*i]){ cnt[s[2*i+d]-97]++; i++; } c=i; for(i=31;i>-1;i--){ c -= cnt[i]; cnt[i]=c; } i=0; while(s[2*i]){ t[2*cnt[s[2*i+d]-97]] = s[2*i]; t[2*cnt[s[2*i+d]-97]+1] = s[2*i+1]; cnt[s[2*i+d]-97]++; i++; } memcpy(s, t, 2*i); } } int main(void) { int i; char s[1001]; scanf("%d",&i); while(i--){ scanf("%s", &s); rxSort(s); printf("%s\n",s); } return 0; }

먼저 첫 포문에서 cnt 배열을 초기화 하는데 이는 알파벳을 체크하기 위한 배열로 보입니다. 배열의 크기가 32인 이유는 잘 모르겠네요...

while문에서 해당하는 알파벳의 카운트를 해줍니다. 인덱스 값으로 -97을 해주는데 이는 ASCII 코드에 나오는 알파벳들의 값을 인덱스로 하여 집어넣어 주기 위합입니다.

예를 들어 소문자 a 는 10진수로 97이라는 값을 갖습니다. -97 을 모든 알파벳에 적용한다면 인덱스 0 의 자리 부터 a b c . . . 순으로 인덱스 값을 갖게 되겟죠.

다음으로 나오는 for문에서는 알파벳의 정렬 순서와 알파벳 위치를 설정하는 구문입니다.

전체적인 포문이 d = 1 , 0 순으로 실행됩니다. 이는 2자리 씩 끈은 알파벳 자리에서 뒷 자리 부터 비교하겠다는 의미가 됩니다.

dcba 라는 문자열을 입력 했을 경우 cnt배열은

첫번째로 c 와 a 를 비교하여

01122222... 라는 숫자 열을 갖게 됩니다.

여기서 0 1 2 라는 숫자는 각 알파벳이 표시되어야 하는 순서와 표시될 위치를 의미하죠.

0 1 1 2 2 2 2..

   a    c

순으로 표시 정보를 의미합니다.

두번째로 d b 를 비교하여

00112222... 라는 열이 나오고

위와 마찬가지의 정보를 가집니다.

각 cnt 배열 정보값을 이용하여 마지막 구문에서 표시를 해주면 정렬된 문자열이 표시됩니다.