10진수로 바꾸지 않고 2진수, 8진수 서로 변환하기

1. 문제

 

1373번: 2진수 8진수 (acmicpc.net)

1373번: 2진수 8진수

 

2. 2진수에서 바로 8진수로 바꾸는 알고리즘

 

[진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기! : 네이버 블로그 (naver.com)

[진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기!

 

 

8이 2의 세제곱이기 때문에, 원래 2진수에서 3자리씩 끊어서 각각을 10진수로 바꿔서 더해주면 그 수가 8진수가 된다.

 

1) 주어진 2진수를 뒤에서부터 3자리씩 읽는다.

 

2) 읽은 3자리를 10진수로 바꾸면 그것이 해당 자리의 8진수 자리가 된다.

 

3) 3자리씩 읽어가는데, 맨 앞에서 3자리가 안채워진다면, 0으로 채워준다.

 

4) 2)에서 바꾼 모든 8진수를 차례대로 붙여주면 2진수를 8진수로 바꾼것이 된다.

 

예를 들어 11101을 생각해보면..

 

뒤에서부터 3자리씩 읽는데 먼저 11/101이 된다.

 

 

읽어낸 101을 10진수로 바꿔줄려면, 맨 앞 자리는 $2^{2}$ 자리이고, 두번째는 $2^{1}$자리이고 3번째는 $2^{0}$자리이다.

 

그래서 4 + 0 + 1 = 5가 된다.

 

마찬가지로 나머지도 3자리만 읽어준다

 

그런데 11로 2자리밖에 없어서 앞에 0을 붙여서 011로 읽어준다

 

 

그래서 11101은 8진수로 35가 된다.

 

 

3. 풀이

 

뒤에서부터 3자리씩 읽어서, 10진수 문자열로 바꿔서 정답 문자열에 계속 붙여준다

 

from sys import stdin

s = stdin.readline().rstrip()

n = len(s)

eight = ''

three = ''

k = 0

for i in range(n-1,-1,-1):
    
    three += s[i]

    k += 1

    if k == 3:
        
        summation = 0

        for i in range(2,-1,-1):
            
            summation += int(three[i])*(2**i)
        
        eight += str(summation)

        k = 0
        three = ''

if k != 0:
    
    while k != 3:
        
        three += '0'
        k += 1

    summation = 0

    for i in range(2,-1,-1):
        
        summation += int(three[i])*(2**i)    
    
    eight += str(summation)

print(eight[::-1])

 

 

근데 이렇게 문자열로만 해결할려고 하면... 시간복잡도가 상당히 커지는데

 

왜 그런지 생각을 해보면

 

파이썬에서 문자열을 더해주는 연산이 시간복잡도가 O(N) (이상일려나?) 매우 커서 그렇다

 

문자열이 불변이라 새로운 문자열을 만들어서 그래

 

아무튼 주어지는 수의 길이 제한이 1,000,000이라서 더할때마다 길이만큼 시간이 걸리니까 

 

잘못하면 통과를 못한다는 소리

 

그래서 eight라는 정답 문자열에 더해주는 연산을 하지말고,

 

eight를 리스트로 만들어서 append시킨다음에 마지막에 eight에 모인 모든 문자열을 join을 이용해 한번에 문자열로 바꿔준다면...

 

중간에 eight를 더하는 연산을 O(1)에 처리하게 되니 시간복잡도가 매우 줄어들것

 

실제로 4000ms에서 700ms로 감소

 

from sys import stdin

s = stdin.readline().rstrip()

n = len(s)

eight = []

three = []

k = 0

for i in range(n-1,-1,-1):
    
    three.append(s[i])

    k += 1

    if k == 3:
        
        summation = 0

        for i in range(2,-1,-1):
            
            summation += int(three[i])*(2**i)
        
        eight.append(str(summation))

        k = 0
        three = []

if k != 0:
    
    while k != 3:
        
        three.append('0')
        k += 1

    summation = 0

    for i in range(2,-1,-1):
        
        summation += int(three[i])*(2**i)    
    
    eight.append(str(summation))

print(''.join(eight[::-1]))

 

 

파이썬에서는 함수로 아주 쉽게 할 수 있다..

 

s가 2진수이면.. int(s, 2)는 2진수 s를 10진수로 바꿔서 내주고

 

 

oct()함수는 10진수를 8진수로 바꿔준다.

 

 

이때 Oo를 앞에 붙여서 내주기 때문에 index 2번부터 출력해야한다

 

from sys import stdin

print(oct(int(stdin.readline().rstrip(),2))[2:])

 

 

4. 문제2

 

1212번: 8진수 2진수 (acmicpc.net)

1212번: 8진수 2진수

 

 

5. 8진수에서 2진수로 바꾸는 알고리즘

 

2진수에서 8진수로 변환하는 알고리즘을 생각해보면 3자리씩 끊어서 각 3자리를 10진수로 바꾸면 그것이 각각의 8진수가 된다는 것인데

 

그러면 반대로 8진수가 주어졌을때 2진수로 바꿀려면...

 

8진수를 하나씩 읽어서 각 수를 3자리 2진수로 바꿔서 앞에서부터 붙여주면 그만

 

예를 들어 35가 8진수라고 한다면..

 

3 / 5로 하나씩 읽어서

 

3을 3자리 2진수로 바꾸면 011이고

 

5를 3자리 2진수로 바꾸면 101이므로

 

011101이 2진수가 된다.

 

 

6. 풀이

 

주어진 8진수 문자열을 앞에서부터 하나씩 읽어서,

 

그것을 3자리 2진수로 바꿔준다

 

이때 문자열 덧셈 연산을 하지말고, 리스트에 넣어준다음에 마지막에 join으로 문자열로 바꿔줘야 시간안에 통과가능

 

그리고 문제 요구조건에서 0을 제외하고는 앞자리가 1로 시작해야한다고 한다

 

그러면 시작 가능한 경우가

 

첫자리가 0인 경우

 

011111111111111111111111

 

첫자리, 두번째자리가 0인 경우(이걸 놓침)

 

001111111111111111111111

 

2가지가 있다.

 

from sys import stdin

s = stdin.readline().rstrip()

second = []

for c in s:
    
    c = int(c)

    num = 0

    sub = ''

    while c > 0:
        
        q,r = divmod(c,2)
        
        sub += str(r)

        num += 1

        c = q
    
    while num != 3:
        
        sub += '0'
        num += 1
    
    second.append(sub[::-1])


if s != '0':
    
    second = ''.join(second)

    if second[0] == '0' and second[1] == '0':
        print(second[2:])
    
    elif second[0] == '0' and second[1] != '0':
        
        print(second[1:])
    
    else:
        
        print(second)

elif s == '0':

    print('0')

 

 

마찬가지로 파이썬은 아주 쉽게 bin와 int를 이용해서 해결할 수도 있다

 

int(s,8)하면 8진수 s를 10진수로 바꿔주고

 

bin()함수로 10진수를 2진수로 바꿔준다

 

 

 

이 때 앞에 0b가 붙어 나오니까 index 2번부터 출력해줘야한다

 

from sys import stdin

s = bin(int(stdin.readline().rstrip(),8))[2:]

print(s)