5658

static int N, K;
static int muls[] = { 0x1, 0x10, 0x100, 0x1000, 0x10000, 0x100000, 0x1000000 };
static int translator[255];
static long long ans[28];
 
static void init_translator(void)
{
    char values[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                    'A', 'B', 'C', 'D', 'E', 'F' };
 
    int v = 0;
    for (int i = 0; i < sizeof(values) / sizeof(char); i++)
        translator[values[i]] = v++;
}
 
static int cmp(const void * p1, const void * p2)
{
    long long n1 = *(long long *)p1;
    long long n2 = *(long long *)p2;
 
    return (int)(n2 - n1);
}
 
static long long solution(void)
{
    char tmp[32];
    list<char> treasure;
 
    scanf("%d %d", &N, &K);
    scanf("%s\n", tmp);
    for (int i = 0; i < N; i++)
        treasure.push_back(tmp[i]);
     
    int len = N / 4; //한변의 길이
    int arr_len = 0;
    list<char>::reverse_iterator s, e;
    memset(ans, -1, sizeof(ans));
 
    for (int cnt = 0; cnt <= len; cnt++)
    {
        int idx = 0;
        long long value = 0;
 
        e = treasure.rend();
        for (s = treasure.rbegin(); s != e; s++)
        {
            int v = translator[*s];
            value += v * muls[idx++];
 
            if (idx == len)
            {
                for (int i = 0; i < N; i++)
                {
                    if (value == ans[i])
                        break;
 
                    if (ans[i] == -1)
                    {
                        ans[arr_len++] = value;
                        break;
                    }
                }
 
                idx = 0;
                value = 0; //value 초기화
            }
        }
 
        treasure.push_front(treasure.back());
        treasure.pop_back();
    }
 
    qsort(ans, arr_len, sizeof(long long), cmp);
    return ans[K - 1];
}

시계 방향으로 회전하는 형태를 모델링하기 위해 빈번한 복사가 있는 벡터보다는 리스트로 구현을 하였다.

자석관련 문제와 같은 방식이다.

 

각변에 있는 16진수 값을 10진수로 변환하는 것 자체는 어렵지 않지만,

한가지 까다로웠던 점은 중복 체크를 하는 것이었다.

문제 조건 상 나올 수 있는 최대값은 0x0fffffff 이고 이는 268,435,455‬ 이므로 이 정도의 길이를 갖는 배열을 선언하는 것자체는 문제의 메모리 조건 상 불가능 하다.

하지만 문제 조건 상 나올 수 있는 16진수 값의 개수는 최대 28개 이다.

이는 단순한 탐색으로도 오랜 시간이 걸리지 않는 작업이므로 좀 허접해 보이지만 이렇게 중복체크를 하였다.

 

마지막은 이렇게해서 형성된 배열을 내림차순으로 정렬만 하면 되는데, qsort()로 간단히 할 수 있다.

 

이 문제에서 한가지 유념할 점은 아래이다.

리스트에 변화가 있을 시, end() / rend() 역시 바꿔주어야함.

 

보통 벡터나 리스트를 순회할 시 for문에 start != vector.end(); 와 같은 조건식 보다는

vector.end()의 리턴 값을 반복자 변수에 저장해서 이와 비교하는식으로 주로 코드를 작성하는데,

이는 반복문이 길어질 시 루프 종료 조건을 검사하기 위한 함수 호출을 자제하기 위해서이다. 물론 실제로 의미있을 만한 시간차이가 있는지 직접 확인해보지는 않았지만 말이다.

어쨌든 이렇게 해도 별 상관은 없을 것이라 생각했지만 그렇지 않았고, 이를 몰라 꽤나 삽질을 했다.