문제
2진수가 주어지면 8진수로 변환하여 출력하라.
입력
2진수 문자열이 주어진다 (최대 20자리).
출력
8진수로 변환한 결과를 출력한다.
예제
| 입력 | 출력 |
|---|---|
11001100 | 314 |
풀이
2진수를 뒤에서 3자리씩 끊어 각 그룹을 8진수 한 자리로 변환한다.
- 문자열 뒤에서 3자리씩 끊어
4*첫째 + 2*둘째 + 1*셋째로 변환한다 - 변환된 값을 스택에 넣는다 (역순 출력을 위해)
- 남은 자릿수(1~2자리)도 같은 방식으로 처리한다
- 스택에서 꺼내며 순서대로 출력한다
핵심 아이디어: 2진수 3자리 = 8진수 1자리이므로, 뒤에서 3자리씩 그룹핑하면 O(N)에 변환된다.
코드
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
using namespace std;
int main(void)
{
string str;
cin >> str;
vector<int> num(3);
stack<int> stk;
int res = 0;
int power = 1;
int tmp = 0;
while (str.size() > 2)
{
tmp = 0;
num.assign(3, 0);
num[0] = str[str.size() - 3] - '0';
num[1] = str[str.size() - 2] - '0';
num[2] = str[str.size() - 1] - '0';
tmp += num[0] * (int)pow(2, 2);
tmp += num[1] * (int)pow(2, 1);
tmp += num[2] * (int)pow(2, 0);
stk.push(tmp);
str.erase(str.size() - 3, 3);
}
tmp = 0;
if (str.size() == 1)
{
str[0] -= '0';
if (str[0])
stk.push(1);
}
else if (str.size() == 2)
{
str[0] -= '0';
str[1] -= '0';
tmp += str[0] * (int)pow(2, 1);
tmp += str[1] * (int)pow(2, 0);
stk.push(tmp);
}
while (!stk.empty())
{
cout << stk.top();
stk.pop();
}
}복잡도
- 시간: O(N) (N: 2진수 자릿수)
- 공간: O(N/3)