ABC 042_B. Iroha Loves Strings (ABC Edition)

* 최적화된 답은 아니지만 공부한 것들의 기록을 위한 코드와 관련 지식을 정리하고자 합니다.

* 출제자가 원하는 답까지는 못 가도 일단 풀어내기 위한 노력을 하려 합니다. 한 단계 성장을 위해서 !

* 회사에서 C 쓰다 요즘 CPP을 쓰다보니까 두 언어가 섞여 쓰게 되었습니다. 충분히 고려하면서 cpp을 쓰기엔 문제 풀기에도 바쁜 시간..T^T

 

B.Iroha Loves Strings (ABC Edition)

 

#include <iostream>
#include <cstring>
using namespace std;


class Bucket
{
public:
    Bucket(void)
    {
        memset(bucket, 0, sizeof(bucket));
    }
    string * GetSourceArr (void) {
        return input_arr[_GetSourceIdx()];
    }
    string * GetDestArr (void) {
        return input_arr[_GetDestIdx()];
    }
    string input_arr[2][101];
    uint32_t bucket[26][101];
private:
    uint32_t _GetSourceIdx (void) {
        return buffer_idx;
    }
    uint32_t _GetDestIdx (void)
    {
        buffer_idx = (buffer_idx + 1) %2;
        return buffer_idx;
    }
    uint32_t buffer_idx = 0;
    
};

int main(void)
{
    uint32_t N = 0 , L = 0;
    Bucket bucket;
    cin >> N >> L;
    for(uint32_t i = 0 ; i < N; i++)
    {
        string tmp;
        string * input = bucket.GetSourceArr();
        cin >> tmp;
        input[i] = tmp;
    }

    for(int strIdx = L-1 ; strIdx >= 0; strIdx--)
    {
        string * srcBuf = bucket.GetSourceArr();
        for(uint32_t i = 0 ; i < N; i++)
        {
            string tmp = srcBuf[i];
            uint32_t idx =  tmp[strIdx] - 'a';
            bucket.bucket[idx][0]++;
            bucket.bucket[idx][bucket.bucket[idx][0]] = i;
        }

        string * dstBuf = bucket.GetDestArr();
        uint32_t dstIdx = 0;
        for(uint32_t i = 0 ; i < 26; i++)
        {
            uint32_t count = bucket.bucket[i][0];
            bucket.bucket[i][0] = 0;
            for(uint32_t j = 1 ; j <= count ; j++)
            {
                dstBuf[dstIdx++] = srcBuf[bucket.bucket[i][j]];
            }
        }
    }

    string * srcBuf = bucket.GetSourceArr();
    for(uint32_t i= 0 ; i < N ; i++)
    {
        cout << srcBuf[i];
    }
    cout << endl;
    return 0;
}

- 사실 오랜만에 알고리즘 문제를 풀다보니까 머리 속에서 문제도 정리가 안되고 어느 거부터 순서대로 해야할지 감이 잘 안 잡힌다. 

입력된 문자열들을 사전 순으로 적은 순서로 출력하는 문제.

문자열은 100까지의 길이를 가질 수 있다.

문자열의 사전 순서 비교를 위해 radix sorting 을 이용했다. input_arr 라는 2차원 배열을 선언하여 2개의 버퍼를 사용하였다. 

source buf 를 이용하여 i번째 기수 정렬을 진행, destnation buf에 정렬.

i+1 번째 기수 정렬할 때, dest buf를 src buf로 하여 i번째에서 src buf 로 사용된 버퍼를 dest buf 로 한다. 

linked list 로 정렬해도 되지만, input의 개수가 충분히 배열로 선언하여 작성하여도 될 정도이기 때문에 배열로 사용하였다.

 

기수 정렬을 0~9 까지 숫자에 대해서 진행한 것을 

a~z 까지 26 개의 bucket으로 진행하였다.

 

이후 정렬이 다 끝나면 buffer의 맨 앞 부터 그대로 출력하면 된다.

 

- radix sorting 을 좀 더 다듬어서 작성할 필요가 무척 생겼다.