오늘은 Spring 입문 1주차 스터디와 함께 알고리즘 문제 풀이를 진행했다. 오늘 풀어본 알고리즘 문제는 바로 "3진법 뒤집기"였다.
문제 속으로 풍덩
문제 자체는 간단했다. 주어진 자연수 n을 3진법으로 변환한 뒤, 그 3진법 숫자를 앞뒤로 뒤집고, 다시 10진법으로 변환하여 반환하는 문제였다. 3진법 변환은 숫자를 3으로 계속 나누면서 나머지를 기록하는 과정을 반복하면 된다. 이 나머지를 문자열에 계속 추가하면 자연스럽게 "뒤집힌" 3진법 숫자를 얻을 수 있다. 이 3진법 숫자를 다시 10진법으로 변환하는 것은 각 자리수에 해당하는 3의 거듭제곱을 곱하여 모두 더하면 된다.
예를 들어, 45라는 숫자가 주어졌다고 가정해보자.
- 45를 3으로 나누면 몫은 15, 나머지는 0이다. 문자열에 "0"을 추가한다.
- 15를 3으로 나누면 몫은 5, 나머지는 0이다. 문자열에 "0"을 추가한다. 현재 문자열은 "00"이다.
- 5를 3으로 나누면 몫은 1, 나머지는 2이다. 문자열에 "2"를 추가한다. 현재 문자열은 "002"이다.
- 1을 3으로 나누면 몫은 0, 나머지는 1이다. 문자열에 "1"을 추가한다. 현재 문자열은 "0021"이다.
이렇게 얻어진 "0021"은 뒤집힌 3진법 숫자이다. 이제 각 자리에 해당하는 3의 거듭제곱을 곱하여 더하면 된다.
- 0 * 3^3 + 0 * 3^2 + 2 * 3^1 + 1 * 3^0 = 0 + 0 + 6 + 1 = 7
따라서 45를 3진법으로 뒤집은 후 10진법으로 표현한 수는 7이 된다.
예상치 못한 암초
문제 로직 자체는 어렵지 않았지만, 살짝 열받는 부분이 있었다. 문제에서 주어진 입력 값의 범위가 1억 이하의 자연수였는데, 3진법으로 변환하는 과정에서 숫자가 커지면서 오버플로우가 발생하는 문제가 발생했다. 이 때문에 예상치 못한 오류가 계속 발생하여 디버깅 시간을 꽤 잡아먹었다. 변수의 자료형을 더 큰 범위로 변경하여 문제를 해결했지만, 입력 값의 범위에 따라 발생할 수 있는 오버플로우 문제를 간과하지 않도록 주의해야겠다는 교훈을 얻었다.
마무리
오늘은 3진법 뒤집기 문제를 풀면서 기본적인 진법 변환 로직을 다시 한번 상기할 수 있었다. 또한, 문제 해결 과정에서 발생한 오버플로우 문제를 통해 자료형 선택의 중요성을 깨달았다. 앞으로 알고리즘 문제를 풀 때 입력 값의 범위를 꼼꼼히 확인하고, 발생 가능한 예외 상황에 대해 미리 대비하는 습관을 들여야겠다. Spring 스터디도 꾸준히 참여하여 backend 개발 실력을 키워나가야겠다.