프로그래머스 입문 120886 A로 B 만들기

문제

출처

소문자로 이루어진 길이가 같은 두 문자열 before와 after가 매개변수로 주어진다.
before의 알파벳을 재배열해 after를 만들 수 있으면 1을, 만들 수 없으면 0을 반환한다.

before	after	result
“olleh”	“hello”	1
“allpe”	“apple”	0

풀이

알파벳 빈도 배열로 비교하기

#include <string.h>

int solution(const char* before, const char* after)
{
    int len = strlen(before);
    int letter_counts[26] = { 0 };

    for (int i = 0; i < len; i++)
    {
        letter_counts[before[i] - 'a']++;
    }

    for (int i = 0; i < len; i++)
    {
        int letter_index = after[i] - 'a';

        letter_counts[letter_index]--;

        if (letter_counts[letter_index] < 0)
        {
            return 0;
        }
    }

    return 1;
}

문자열이 소문자로만 이루어져 있으므로 가능한 문자의 종류는 26개뿐이다.
before[i] - 'a'는 문자를 0부터 25까지의 인덱스로 바꾸는 계산이다.
먼저 before를 순회하며 각 문자가 몇 번 등장하는지 배열에 기록한다.

그다음 after를 순회하며 같은 인덱스의 값을 하나씩 감소시킨다.
감소한 값이 0보다 작아졌다면 after에 필요한 문자가 before에 부족하다는 뜻이다.
이 경우 after를 만들 수 없으므로 0을 반환한다.

반복문을 끝까지 통과했다면 부족한 문자가 없다는 뜻이다.
따라서 before의 알파벳을 재배열해 after를 만들 수 있으므로 1을 반환한다.

두 문자열을 정렬해서 비교하기

#include <stdlib.h>
#include <string.h>

int compare_chars(const void* a, const void* b)
{
    return *(const char*)a - *(const char*)b;
}

int solution(const char* before, const char* after)
{
    int len = strlen(before);
    char* sorted_before = malloc(len + 1);
    char* sorted_after = malloc(len + 1);

    memcpy(sorted_before, before, len + 1);
    memcpy(sorted_after, after, len + 1);

    qsort(sorted_before, len, sizeof(char), compare_chars);
    qsort(sorted_after, len, sizeof(char), compare_chars);

    int result = strcmp(sorted_before, sorted_after) == 0 ? 1 : 0;

    free(sorted_before);
    free(sorted_after);

    return result;
}

문제에서 두 문자열의 길이가 같다고 전제하고 있다.
따라서 before의 문자로 after를 만들 수 있다는 말은 문자 배치 순서만 다를 뿐 문자 구성은 같다는 뜻이다.

매개변수로 주어진 문자열은 const char*이므로 원본 문자열을 직접 정렬할 수 없다.
그래서 malloc으로 복사할 공간을 만들고, memcpy로 문자열을 복사한 뒤 정렬한다.

환경에 따라 malloc 대신 VLA(가변 길이 배열)를 사용할 수도 있다.
하지만 VLA는 C89와 MSVC에서 지원되지 않으므로 좀 더 범용적인 동적 할당을 사용했다.