[UVA] 공통된 변경 문자열 (Common Permutation)

오늘은 알고리즘을 몇 개 풀어봐서 올려보겠습니다. 

아직은 쉬운 것 밖에 풀지 못해서 더욱 분발해야겠습니다.  

다행스럽게도 하나씩 풀어가는 재미가 조금은 느껴지네요. ^^

참고 : uva에 제출해서 확인해 보지는 않았습니다. 

- 문제 -
두개의 문자열 a, b가 주어졌을 때 글자의 순서를 바꿔서 

a의 부분 문자열도 만들 수 있고 b의 부분 문자열도 만들 수 있는 

것 중 가장 긴 문자열 x를 출력하라. 

입력 예) pretty women walking down the street

출력 예)  e nw et

#include <stdio.h> #include <stdlib.h> #include <string.h> #define INPUT_NUM 6 // 임의로 정한 입력 데이터 수 char* chkChar(char a[], char b[]) // 두 문자열에서 공통된 문자를 찾는 함수 { int aNum, bNum; int i, j, cnt = 0; char result[50] = {0,}; aNum = strlen(a); bNum = strlen(b); for(i=0; i<aNum; i++) { for(j=0; j<bNum; j++) { if( *(a+i) == *(b+j) ) { result[cnt++] = *(b+j); break; } } } return result; } char* sorting(char input[], int length) // 공통된 문자들로 이루어진 문자열을 정렬하는 함수 { int i, j; char temp; for(i=0; i<length; i++) { for(j=i+1; j<length; j++) { if(input[i] > input[j]) { temp = input[i]; input[i] = input[j]; input[j] = temp; } } } return input; } int main() { char arr[50][1000] = {0,}; char real[50][1000] = {0,}; int i = 0,j = 0; char result[1000] = {0,}; int resultNum = 0; char temp; for(i=0; i< INPUT_NUM; i++) scanf("%s", arr[i]); for(i=0; i<INPUT_NUM; i+=2) { strcpy(result, chkChar(arr[i], arr[i+1])); resultNum = strlen(result); strcpy(result, sorting(result, resultNum)); } return 0; }