정수가 하나 주어졌을 때, 이를 16진수(hexadecimal) 문자열로 변환하는 알고리즘을 설계해야 합니다. 이때 음수가 입력되는 경우에는 2의 보수(two's complement) 방식을 적용하여 처리합니다.
예를 들어 입력값이 254와 -12라면, 결과는 각각 fe와 fffffff4가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 입력값
num1이 0이라면 즉시"0"을 반환합니다. num에num1을 저장합니다.- 빈 문자열
s를 준비합니다. num이 0이 아닐 때까지 다음 과정을 반복합니다.temp = num % 16으로 나머지를 구합니다.temp가 9 이하라면 해당 숫자에 대응하는 숫자 문자('0'~'9')를s에 추가합니다.- 그렇지 않다면(10~15) 대응하는 알파벳 문자('a'~'f')를
s에 추가합니다. num을 16으로 나눕니다.
- 반복이 끝나면 문자열
s를 뒤집습니다(낮은 자릿수부터 채워졌기 때문입니다). s를 반환합니다.
핵심 포인트: 부호 없는 정수로의 형변환
여기서 중요한 비법은 int형 음수를 unsigned int(u_int)로 변환한다는 점입니다. C++에서 음수를 부호 없는 정수로 캐스팅하면 자동으로 2의 보수 표현이 되므로, 별도의 복잡한 연산 없이 일반적인 16진수 변환 로직을 그대로 사용할 수 있습니다. 예를 들어 -12를 32비트 unsigned 값으로 바꾸면 4294967284가 되고, 이를 16진수로 나타내면 fffffff4가 됩니다.
구현 예제
아래 코드를 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string toHex(int num1){
if (num1 == 0)
return "0";
u_int num = num1; // 음수도 2의 보수 기반의 unsigned 값으로 변환됨
string s = "";
while (num) {
int temp = num % 16;
if (temp <= 9)
s += (48 + temp); // '0'(ASCII 48)부터 '9'까지 매핑
else
s += (87 + temp); // 'a'(ASCII 97)부터 'f'까지 매핑
num = num / 16;
}
reverse(s.begin(), s.end());
return s;
}
};
main(){
Solution ob;
cout << (ob.toHex(254)) << endl;
cout << (ob.toHex(-12));
}코드 동작 원리 살펴보기
문자를 추가하는 부분의 숫자가 궁금할 수 있습니다. 문자 '0'의 ASCII 코드는 48이므로, 48 + temp를 통해 0~9 사이의 값을 숫자 문자로 만들 수 있습니다. 마찬가지로 소문자 'a'의 ASCII 코드는 97이며, 87 + 10 = 97이므로 87 + temp를 사용하면 10~15 사이의 값을 'a'~'f'로 매핑할 수 있습니다.
입력
254 -12
출력
fe fffffff4
마무리
이 알고리즘은 한 번의 나눗셈 연산마다 자릿수가 하나씩 결정되므로, 시간 복잡도는 O(log₁₆ n), 즉 32비트 정수 기준 최대 8번의 반복으로 해결됩니다. 공간 복잡도 역시 결과 문자열 길이에 비례하여 O(1)로 간주할 수 있어 매우 효율적입니다. 또한 C++에서는 std::hex나 sprintf, std::format 등의 표준 라이브러리를 활용하면 같은 작업을 더 간단하게 수행할 수도 있습니다.