문제 설명
정수 n이 주어졌을 때, 다음 연산을 수행한 결과에서 n번째 정수를 반환해야 합니다. 정수 1부터 시작하여 9, 19, 29처럼 숫자 9를 포함하는 모든 정수를 제거하면 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ... 과 같은 새로운 수열이 만들어집니다. 이때 1이 첫 번째 정수라는 점에 유의해야 합니다.
예를 들어 입력이 9라면, 수열에서 9는 이미 제거되었으므로 9번째 정수는 10이 됩니다.
접근 방법: 9진법 변환
이 문제의 핵심 아이디어는 바로 9진수 변환입니다. 9를 포함하지 않는 수열은 각 자릿수가 0~8 사이의 값만 가질 수 있으므로, n번째 항은 단순히 n을 9진법으로 표현한 값과 같습니다.
알고리즘은 다음과 같습니다.
결괏값 ret을 0으로, 자릿수 가중치 s를 1로 초기화합니다.
n이 0이 아닌 동안 다음 과정을 반복합니다.
ret := ret + (n mod 9) × s
n := n / 9
s := s × 10
반복이 종료되면 ret에 담긴 값이 곧 정답이며, 이를 반환합니다. 시간 복잡도는 O(log₉ n)으로 매우 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int newInteger(int n) {
int ret = 0;
lli s = 1;
while (n) {
ret += (n % 9) * s;
n /= 9;
s *= 10;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.newInteger(120));
}입력
120
출력
143
결과 해석
입력 120을 9진법으로 변환하면 143이 됩니다. 실제로 1×81 + 4×9 + 3 = 120이 성립하므로, 9가 포함되지 않은 수열에서 120번째 정수는 143임을 확인할 수 있습니다.