애너그램 만들기 (1919번)

1. 문제

두 영어 단어가 철자의 순서를 뒤바꾸어 같아질 수 있을 때, 그러한 두 단어를 서로 애너그램 관계에 있다고 한다. 예를 들면 occurs 라는 영어 단어와 succor 는 서로 애너그램 관계에 있는데, occurs의 각 문자들의 순서를 잘 바꾸면 succor이 되기 때문이다.

한 편, dared와 bread는 서로 애너그램 관계에 있지 않다. 하지만 dared에서 맨 앞의 d를 제거하고, bread에서 제일 앞의 b를 제거하면, ared와 read라는 서로 애너그램 관계에 있는 단어가 남게 된다.

두 개의 영어 단어가 주어졌을 때, 두 단어가 서로 애너그램 관계에 있도록 만들기 위해서 제거해야 하는 최소 개수의 문자 수를 구하는 프로그램을 작성하시오. 문자를 제거할 때에는 아무 위치에 있는 문자든지 제거할 수 있다.

첫째 줄과 둘째 줄에 영어 단어가 소문자로 주어진다. 각각의 길이는 1,000자를 넘지 않으며, 적어도 한 글자로 이루어진 단어가 주어진다.

2. 포인트

1) 입력 문자열 길이가 같은경우+다른경우 

2) 문자열1을 기준으로 문자열2와 각 문자 비교
  - 선택정렬처럼 한 개 씩 비교
  - 같은 문자 발견 시, 문자열 2의 해당 문자를 NULL로 바꿔준다.
  - 동일한 값 찾은 것 카운드 (아래코드에서 변수 k)
3) 문자열 길이 구하기
  ex) str[100] = {a,b,NULL}  → strlen(str) : 2  /  sizeof(str) : 100  (2로 오해 금지)

3. 소스코드

#include <stdio.h>

#define LEN 1000

int main(void) 

{

int i, j;

int k = 0;

int len1 , len2;

char str1[LEN];

char str2[LEN];

scanf("%s %s", str1, str2);

 len1 = strlen(str1);

 len2 = strlen(str2);

//  문자열1을 기준으로 문자열2와 각 문자 비교

for (i = 0; i < len1; i++)

{

for (j = 0; j < len2; j++)

{

if (str1[i] == str2[j])

{

str2[j] = NULL;

k++;

break;

}

}

}

printf("%d", len1+len2 - k*2);

return 0;

}