문제:
Write a function that converts the initial portion of the string pointed by str to int representation.
• str is in a specific base given as a second parameter.
• excepted the base rule, the function should work exactly like ft_atoi.
• If there’s an invalid argument, the function should return 0. Examples of invalid
arguments :
◦ base is empty or size of 1;
◦ base contains the same character twice ;
◦ base contains + or - or whitespaces;
Allowed functions : None
Here’s how it should be prototyped : int ft_atoi_base(char str, char base);
문제를 요약하면 ft_atoi_base의 파라미터로 문자, base(진법)가 들어오면 문자를 해당 base로 변환을 한 뒤 10진수 정수로 바꿔야 한다.
예를 들어 입력 문자가 " \n \n +--+-f9zxc#$%\"이고 입력 진법이 "0123456789abcdef"라고 하자.
앞의 white space(공백 문자)를 제거하고 부호처리를 한 뒤 (-가 3개니까 음수) 해당 base로 뒤의 문자가 10진수로 몇인지 계산해야한다.
이때 f9는 base에 있지만 zxc#$%는 base에 해당하지 않으므로 f9까지만 읽어들여야 한다.
들어온 base의 길이는 16이므로 16진수인 것을 알 수 있고, f = 15번째, 9는 9번째 문자열이므로 f9 = (16 ^ 1) * 15, 9 = (16 ^ 0) * 9인 것을 알 수 있다.
*주의: 다음과 같은 입력도 가능하다.
str : ' -++-pvifwe' | base : pvifskwm
답: 670
다음 두가지가 주요한 아이디어였고, 나머지는 그냥 조건대로 구현하면 된다.
1. 중복 판단
많은 사람들이 base내에 중복 문자가 있는지 알기 위해서 O(n ^ 2)의 탐색을 시도했다.
하지만 나는 O(n)만에 가능한 판별법을 사용했다. (메모리를 약간 더 먹긴 한다.)
그 방법은 길이가 127인 배열 하나를 만들고 모두 0으로 초기화한다.
그 다음 특정 문자가 들어오면 그 문자의 아스키코드에 해당하는 인덱스를 1로 만든다.
그 후 또 그 문자가 들어왔을 때 그 인덱스 번호는 1이므로 중복됨을 알 수 있다.
example)
a가 들어옴 > array: 0 0 0 0 . . . . (97번째 인덱스 0 > 1) 1 0 0 0
또 a가 들어옴 > array: 0 0 0 0 . . . . (97번째 인덱스가 1임을 확인) 1 0 0 -> return 0
2. 진법 변환
우선 문자열로 들어오기 때문에 정수와 다르게 앞에서부터 읽어들일 수 있다.
"123"라는 문자열이 들어왔고, 10진법이라고 생각했을 때, 우리는 간단하게 (10 ^ 2) * 1 + (10 ^ 1) * 2 + (10 ^ 0) * 3 임을 알 수 있다.
일반화하면 문자열 "c1 c2 c3 ... ck ..."가 들어오고 base가 "b1 b2 b3 ... bn"이라고 했을 때
a. ck가 base의 몇 번째 문자열인지 알아야한다.
b. base의 길이가 몇인지 알아야한다 (n진법인지 알아야 한다.)
이 두가지를 알면 다음과 같이 쉽게 구할 수 있다.
1. answer = 0 으로 초기화
2.
while 문자열이 끝날 때까지
answer *= base의 길이
answer += ck의 base에서의 위치
전체 코드
int atob(char *str, char *base, int base_len)
{
int i;
int base_i;
int ans;
int minus;
i = 0;
base_i = 0;
ans = 0;
minus = 1;
//white space 제거
while (str[i] == ' ' || (str[i] >= 9 && str[i] <= 13))
i++;
//minus 판별
while (str[i] == '-' || str[i] == '+')
if (str[i++] == '-')
minus *= -1;
//진법 변환
while (str[i] != '\0')
{
base_i = -1;
while (base[++base_i] != '\0')
if (str[i] == base[base_i])
break ;
if (base[base_i] == '\0')
break ;
ans *= base_len;
ans += base_i;
i++;
}
return (minus * ans);
}
int valid_base(char *base)
{
int is_dup[127];
int idx;
idx = 0;
while (idx < 127)
is_dup[idx++] = 0;
idx = 0;
while (base[idx] != '\0')
{
if ((base[idx] == '+') || (base[idx] == '-'))
return (0);
else if (base[idx] == ' ' || (base[idx] >= 9 && base[idx] <= 13))
return (0);
// 중복 판단
else if (is_dup[(int) base[idx]] == 1)
return (0);
else
is_dup[(int) base[idx]] = 1;
idx++;
}
if (idx == 0 || idx == 1)
return (0);
return (1);
}
int ft_atoi_base(char *str, char *base)
{
int base_len;
int nbr;
// 유효한 진법인지 검사
if (!valid_base(base))
return (0);
// n진법인지 계산
base_len = 0;
while (base[base_len] != '\0')
base_len++;
// white space & 부호처리 후 진법 변환
nbr = atob(str, base, base_len);
return (nbr);
}