프로그래머스 Level 2 : 큰 수 만들기 C언어

▶문제 : 코딩 테스트 연습 - 큰 수 만들기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 큰 수 만들기

 

▶코드 작성

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

char *solution(const char *number, int k)
{
    char *answer = (char *)malloc(strlen(number));
    strcpy(answer, "");//answer문자열 초기화

    int i, cnt = 0, len = 0;//cnt:문자열에서 뺀 수의 개수 , len:answer문자열의 길이
    char max, index;
    char *temp = number;
    while (k > cnt && strlen(number) - k > len)
    {
        max = '0';
        index = i = 0;
        while (1)
        {
            if (max < temp[i])//temp문자열의 앞에서부터 큰 수 찾기
            {
                max = temp[i];
                index = i;//큰 수의 자리
                if (max == '9') break;//9가 가장 큰 수 이므로 찾으면 종료
            }
            if (i == k - cnt) break;//i와 뺄 수 있는 개수가 같으면 종료
            i++;
        }
        cnt += index;//문자열에서 뺀 수의 개수 더해주기
        answer[len++] = max;//큰 수를 문자열에 추가
        temp = temp + index + 1;//answer문자열에 추가한 수의 다음 자리부터 다시 반복
    }
    answer[len] = '\0';
    if (strlen(number) - k > len)
    {//숫자 전체의 길이에서 k를 뺀 값이 더 크면 나머지 숫자를 붙여줌
        strcat(answer, temp);
        answer[strlen(number) - k] = '\0';
    }

    return answer;
}

 

▶해석

문제 풀이의 방식은 number문자열의 앞에서부터 큰 수를 골라내어 answer문자열에 추가하고, 작은 수들은 다 뺐는데 문자 길이가 모자라면 나머지 숫자들을 뒤에 붙여주는 방식이다.

 

while문으로 cnt가 문자열에서 뺀 수의 개수이므로 k보다 작을 때 반복하고, len이 answer문자열의 길이인데 number문자열의 길이에서 k를 뺀 값은 출력할 문자열의 개수이므로 그 길이보다 len값이 작아야 한다.

while (k > cnt && strlen(number) - k > len)

 

i=0에서부터 큰 수를 찾아주는데 max에 큰 수를 저장하고, index에 큰 수의 자리를 저장한다. max가 9일 때 더 이상 큰 수는 없으므로 종료해준다.

k에서 cnt를 뺀 값은 현재 빼야 하는 수의 개수이므로 i가 같을 때까지 반복한다.

while (1)
{
    if (max < temp[i])
    {
        max = temp[i];
        index = i;
        if (max == '9') break;
    }
    if (i == k - cnt) break;
    i++;
}

 

temp포인터를 이용하여 큰 수를 찾는 위치를 앞당겼다. 예를 들어 temp="42532"에서 큰 수를 5로 찾았다고 한다면 index는 2이므로 숫자 5의 다음 자리인 3부터 큰 수를 찾게 하려면 temp포인터에 index를 더하면 temp="532"가 되고 거기에 +1을 하면 temp="32"가 되어 5 다음 숫자부터 다시 큰 수를 찾게 한다.

temp = temp + index + 1;

 

위 while반복으로 다 정리가 되면 좋겠는데 만약 len값이 출력할 문자열의 길이보다 작으면 남은 숫자들을 answer뒤로 붙여주어야 한다. 예를 들어 number="43862" , k=2일 때 while반복문으로 4,3을 빼서 2번을 뺐으므로 종료가 되어 answer문자열에는 "8"이 남는다. 남은 "62"는 temp문자열에서 가져올 수 있다.

if (strlen(number) - k > len)
{
    strcat(answer, temp);
    answer[strlen(number) - k] = '\0';
}