1373)2진수 8진수

https://www.acmicpc.net/problem/1373

2진수를 8진수로 변환하는 문제다.

학교에서 8진수를 2진수를 변환하는 방법에 대해 배웠는데 약간 응용해보고자 한다.

각 8진수와 이진수가 대응되는 모습을 표현했다.

0 : 000 , 4 : 100

1 : 001 , 5 : 101

2 : 010 , 6 : 110

3 : 011 , 7 : 111

8진수로 13을 표현할 때 위 테이블을 사용하면 편하게 바꿀 수 있다.

각 자리 숫자를 떼어내 대응되는 이진수로 바꿔주기만 하면 된다.

따라서 8진수 13은 001011이다.

2진수를 8진수로 바꾸는 과정을 생각해보자.

110101을 8진수로 바꾸려면 우선 세 자리씩 끊어야 한다.

110 / 101 로 나뉘는데 굳이 대응되는 8진수를 찾을 필요는 없고

110을 10진수로 바꾸고 101을 10진수로 바꿔 이어붙인 결과가 110101을 8진수로 바꾼 결과와 같다.

애초에 이진수를 3자리씩 끊었기 때문에 결코 8이상이 될 수 없기 때문이다.

길이가 1,000,000 보다 작은 이진수가 주어지는데 뒤에서부터 3자리씩 끊어주면서 8진수로 바꿔주면 된다.

이렇게 세 자리씩 끊다보면 문자열의 앞쪽에는 이진수 비트가 1개 또는 2개가 남는 경우가 있다.

예를들어 1011이나 11011은 세 자리씩 끊어도 가장 앞 자리에 3개로 묶지 못한 비트가 남는다.

이 수들은 앞 자리에 0을 넣어 3개로 묶을 수 있도록 해야 하지만 어차피 0은 계산하지 않기 때문에

이 자체로 10진수로 바꿔주고 이어붙이면 그만이다.

#include<stdio.h>
 
int pow(int n) {
    int a = 1;
    while (n > 0) {
        a *= 2;
        n--;
    }
    return a;
}
 
int main() {
    char binary[1000001];
    int length = 0;
    int digit;
    int octDigit = 0;
    char octa[333334];
    int cnt = 0, t=0;
 
    scanf("%s",binary);
 
    for (int i = 0; binary[i] != NULL; i++) {
        length++;
    }
 
    for (int i = length-1; i>=0; i--) {
        digit = binary[i] - '0';
        octDigit += digit * pow(cnt);
        cnt = (cnt + 1) % 3;
        if (cnt == 0 || i == 0) {
            octa[t++] = octDigit+'0';
            octDigit = 0;
        }
    }
 
    for (int i = t - 1; i >= 0;i--) {
        printf("%c",octa[i]);
    }
    printf("\n");
 
    return 0;
}

런타임 에러가 났었는데 8진수 문자열을 담아낼 배열의 크기를 잘못 계산했기 때문인 듯하다.

주어진 2진수를 3개씩 묶어 10진수로 바꾼 뒤 이어붙여 8진수로 바꾸기 때문에

주어진 2진수 문자열의 길이 length에서 3을 나눈만큼과 묶이지 않은 앞 자리 이진수들을 고려해 1만큼을 더해 배열을 할당받으면

문제가 없다고 생각했다. (length/3+!!(length%3))

문제가 생겼으니 보다 쉽게 8진수 문자열의 최대 크기인 333333개에 맞춰 배열을 할당했다.