[boj] 1373. 2진수 8진수

[boj] 1373. 2진수 8진수

• 문제 링크 : https://www.acmicpc.net/problem/1373
• 사용 언어 : Node.js

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

---

 

1. 문제 분석

2진수를 8진수로 변환하는 문제입니다. 
8진법으로 나타낸 수의 각 자릿수는 2진법 3자리와 매칭하여 변환할 수 있습니다.
$ 8^1 = 2^3 $
앞에서부터 3자리씩 끊어 변환한다면 어렵지 않게 풀이할 수 있을 듯합니다.
하지만 이 문제에는 복병이 하나 있습니다.
"수의 길이가 1,000,000 넘지 않는다."
"이 문장은 길이의 최댓값이 1,000,000이다"와 같습니다.
$ 2^{99 * 10^6} $ 은 프로그래밍 언어 자료형으로 담기에 지나치게 큰 수입니다.
배열에 담기에도 원소가 많습니다.
때문에 문자열 상태에서 3자리씩 잘라 변환 후 다시 문자열로 완성하도록 합니다.

 

---

 

2. 솔루션

(1) 실패 - 메모리 초과 ( 스택 크기 )

 

const fs = require('fs')
let binaryNumbers = fs.readFileSync(process.platform ===
                                    'linux' ? '/dev/stdin' : 'input.txt')
                      .toString().trim()

 function binaryToOctet(binaryNumberArray, remainder = 0) {
     if(binaryNumberArray.length === 0) return ''
     let ret = 0
     if (remainder > 0) {
         let cursor = remainder
         while (cursor > 0) {
             ret += binaryNumberArray[2 - cursor] * 2 ** (cursor - 1)
             cursor--
         }
     } else {
         ret = binaryNumberArray[0] * 2 ** 2 + binaryNumberArray[1] * 2 +
               binaryNumberArray[2]
     }
     return ret.toString() + binaryToOctet(binaryNumberArray.slice(remainder === 0 ? 3 : remainder))
 }

 console.log(binaryToOctet(binaryNumbers, binaryNumbers.length % 3))

 

(2) 성공

 

const fs = require('fs')
let binaryNumbers = fs.readFileSync(process.platform ===
                                    'linux' ? '/dev/stdin' : 'input.txt')
                      .toString().trim()
let answer = ''

const remainder = binaryNumbers.length % 3;
if (remainder === 2) {
    answer += (+binaryNumbers.slice(0, 1) * 2 +
               +binaryNumbers.slice(1, 2)).toString(8)
} else if (remainder === 1) {
    answer += (+binaryNumbers.slice(0, 1)).toString(8)
}

for (let i = remainder; i < binaryNumbers.length; i += 3) {
    answer += (+binaryNumbers.slice(i, i + 1) * 4 +
               +binaryNumbers.slice(i + 1, i + 2) *
               2 + +binaryNumbers.slice(i + 2, i + 3)).toString(8)
}

console.log(answer)

---

마치며

문제 풀이 시 주어진 데이터 크기를 확인하고 메모리 초과가 일어나지 않도록 주의합시다.