[알고리즘 연습] 아나그램 (by C++)

아나그램

• 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다.
• 예를 들어, AbaAeCe 와 baeeACA는 아나그램이다.
• 두 문자열을 받고, 두 문자열이 아나그램이면 'YES'를, 아나그램이 아니면 'NO'를 출력한다.

---

풀이1

#include <stdio.h>

int main() {
    freopen("input.txt", "rt", stdin);
    char a[101],b[101];
    int i,j,flag=1;

    scanf("%s", &a);
    scanf("%s", &b);

    for (i = 0; a[i] != '\0'; i++) {
        for (j = 0; b[j] != '\0'; j++) {
            if (a[i] == b[j]) {
                b[j] = '0';
                break;
            }
        }
    }

    for(i=0; b[i] != '\0'; i++) {
        if (b[i] != '0') {
            flag = 0;
            break;
        }
    }

    if (flag) {
        printf("YES");
    } else {
        printf("NO");
    }

    return 0;
}

- 문자들을 비교하면서 첫 번째 문자에 있는 문자가 두 번째 문자에 있을 경우 해당 문자를 0으로 바꾼다.

- 두 번째 문자열을 보면서 0이 아닌 문자가 있으면 짝이 맞지 않는 문자가 최소 1개 존재한다는 뜻이므로 최종확인을 위한 flag값을 0으로 바꾼다.

- 최종적으로 flag를 이용해 답을 출력한다.

- 시간복잡도 O(N^2)의 효율을 가져 조금 비효율적인 방법이다.

---

풀이2

#include <stdio.h>
#include <algorithm>

int a[60], b[60];
int main() {
    freopen("input.txt", "rt", stdin);
    char str[100];
    int i;

    scanf("%s", &str);
    for(i = 0; str[i] != '\0'; i++) {
        if(str[i] >=65 && str[i] <= 90) {
            a[str[i] - 64]++; 
        } else if (str[i] >= 97 && str[i] <= 122) {
            a[str[i] - 70]++; 
        }
    }

    scanf("%s", &str);
    for(i = 0; str[i] != '\0'; i++) {
        if(str[i] >=65 && str[i] <= 90) {
            b[str[i] - 64]++; 
        } else if (str[i] >= 97 && str[i] <= 122) {
            b[str[i] - 70]++; 
        }
    }

    for(i = 0; i<=52; i++) {
        if (a[i] != b[i]) {
            printf("NO\n");
            exit(0);
        }
    }

    printf("YES\n");

    return 0;
}

- 각 문자열의 알파벳개수를 배열에 저장하여 처리한다.

- A-Z는 아스키코드가 65-90이고, a-z는 아스키코드가 97-122이다. 이를 활용하여 해당 알파벳이 연속되게 배열에 들어갈 수 있도록 한다. (-64, -70)

- 일치하지 않는 것이 발견될 경우 NO를 출력하고 프로그램을 종료한다.

- 일치하지 않는 것이 발견되지 않아 프로그램이 종료되지 않으면 YES를 출력한다.

- 위의 방법보다 시간복잡도가 낮다.