프로그래머스 Level 2 : 가장 큰 수 C언어

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

코딩테스트 연습 - 가장 큰 수

 

▶코드 작성

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

char arr[100000][7];//숫자를 문자열로 저장할 배열
int leng[100000];//arr배열의 자리에 맞는 숫자의 자리수

int compare(char *a, char *b, int n)//문자열 속 숫자 비교
{
    if (a[n] < b[n]) return 1;//a[n]보다 b[n]가 크다면 swap
    if (a[n] == b[n] && n < 3) return compare(a, b, n + 1);//같으면 다음 자리로 이동
    return 0;
}

char *solution(int numbers[], size_t numbers_len)
{
    char *answer = (char *)malloc(numbers_len * 4 + 1);
    char temp[5];
    int sum = 0;

    for (int i = 0; i < numbers_len; i++)
    {
        sprintf(arr[i], "%d", numbers[i]);//숫자를 문자열로
        strcpy(temp, arr[i]);//쓰레기값 방지
        leng[i] = strlen(arr[i]);//문자 길이(숫자 자리수)
        while (strlen(arr[i]) < 4) strcat(arr[i], temp);//4글자 이상으로 맞추기
        sum += numbers[i];
    }

    if (sum == 0) return "0";//배열 원소 합이 0이면 "0"출력

    answer[0] = '\0';//쓰레기값 방지
    for (int i = 0, max; i < numbers_len; i++)//선택정렬
    {
        max = i;
        for (int j = i + 1; j < numbers_len; j++) {
            if (compare(arr[max], arr[j], 0)) max = j;
            //arr[max]보다 arr[j]가 크면 swap
        }

        strncat(answer, arr[max], leng[max]);//arr[max]를 자리수에 맞게 answer에 붙임

        if (max != i) {//i자리는 붙이지 않았으므로 max자리에 바꿔준다
            strcpy(arr[max], arr[i]);
            leng[max] = leng[i];
        }
    }

    return answer;
}

 

▶해석

이 문제의 풀이는 먼저 나와야 할 숫자, 큰 숫자를 찾아서 answer에 붙이는 걸 반복하면 가장 큰 수가 나온다. 하지만 먼저 붙여야 할 숫자를 찾는 것이 문제다.

예를 들어, [30, 303] 이 있으면 답은 "30330" 이고,  [34, 343] 이 있으면 답은 "34343"이다.

첫 예시는 303부터 붙이지만 두 번째 예시는 34부터 붙인다.

 

이런 복잡한 문제를 간단히 바꾸는 방법은 숫자를 문자열로 바꿀 때 모든 문자열을 4자리 이상으로 바꿔주는 것이다.

30이면 "3030", 303이면 "3033", 34이면 "3434", 343이면 "3433", 3이면 "3333" 이런 식으로 바꿔주면

30과 303을 비교할 때 "3030"과 "3033" 중 큰 수는 "3033"이므로 303을 먼저 붙이고,

34와 343을 비교할 때 "3434"과 "3433" 중 큰 수는 "3434"이므로 34부터 붙인다.

 

이러한 방법으로 하는데 sprintf로 숫자를 문자열로 바꿔준 후 while문으로 4자리 이상이 될 때까지 문자열 뒤에 자신을 붙여주었다. 303이면 "303303" 이렇게 말이다.

선택 정렬로 문자열을 4자리까지 compare함수로 재귀를 통해 맨 앞 숫자 [0]부터 비교하였다.

strcat으로 answer에 숫자 문자를 붙여주는데 미리 자릿수를 저장한 leng배열에서 문자를 붙일 길이를 구해 붙여주었다.