프로그래머스 입문 120896 한 번만 등장한 문자

문제

출처

소문자로 이루어진 문자열 s가 매개변수로 주어진다.
문자열에서 한 번만 등장하는 문자를 오름차순으로 정렬해 반환하시오.

s	result
“abcabcadc”	“d”
“abdc”	“abcd”
“hello”	“eho”

풀이

값별 빈도 배열로 세기

#include <stdlib.h>

#define ALPHABET_SIZE 26

char* solution(const char* s)
{
    int letter_counts[ALPHABET_SIZE] = { 0 };
    char* result = malloc(sizeof(char) * (ALPHABET_SIZE + 1));
    int result_index = 0;

    for (int i = 0; s[i] != '\0'; i++)
    {
        letter_counts[s[i] - 'a']++;
    }

    for (int i = 0; i < ALPHABET_SIZE; i++)
    {
        if (letter_counts[i] == 1)
        {
            result[result_index++] = 'a' + i;
        }
    }

    result[result_index] = '\0';

    return result;
}

영어 소문자는 26개이므로 문자별 등장 횟수를 저장할 배열은 26칸이다.
letter_counts[0]은 'a'의 등장 횟수이고, letter_counts[25]는 'z'의 등장 횟수이다.

문자를 배열 인덱스로 바꿀 때는 현재 문자에서 'a'를 뺀다.
ASCII에서 'a'는 97이고 'z'는 122이므로 s[i] - 'a'의 결과는 0부터 25 사이가 된다.

첫 번째 반복문은 문자열을 한 글자씩 보면서 각 알파벳의 빈도를 저장한다.
두 번째 반복문은 저장된 빈도를 인덱스 0부터 25까지 차례대로 확인한다.
이 순서 자체가 'a'부터 'z'까지의 순서이므로 등장 횟수가 1인 문자만 담으면 결과도 자동으로 오름차순이 된다.

배열 인덱스는 'a'로부터 떨어진 거리를 의미한다.
그래서 결과에 넣을 때는 인덱스에 다시 'a'를 더해 실제 문자 값으로 바꾼다.

중첩 반복문

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

char* solution(const char* s)
{
    int len = strlen(s);
    int result_index = 0;
    char* result = malloc(sizeof(char) * (len + 1));

    for (int i = 0; i < len; i++)
    {
        int is_unique = 1;

        for (int j = 0; j < len; j++)
        {
            if (i == j)
            {
                continue;
            }

            if (s[i] == s[j])
            {
                is_unique = 0;
                break;
            }
        }

        if (is_unique)
        {
            result[result_index++] = s[i];
        }
    }

    result[result_index] = '\0';

    for (int i = 0; i < result_index - 1; i++)
    {
        for (int j = 0; j < result_index - 1 - i; j++)
        {
            if (result[j] > result[j + 1])
            {
                char temp = result[j];
                result[j] = result[j + 1];
                result[j + 1] = temp;
            }
        }
    }

    return result;
}

문자 하나를 잡고 문자열 전체를 훑어 중복 여부를 검사하는 방법이다.
중첩 반복문을 사용하므로 시간 복잡도는 O(n^2)로 앞의 O(n) 풀이보다 불리하다.
검사를 통과한 문자만 결과 배열에 담은 뒤 버블 정렬로 오름차순 정렬한다.