주어진 범위에서 모든 자릿수가 고유한 숫자를 찾는 C++ 프로그램

두 개의 수 l과 r이 주어졌을 때, l 이상 r 이하 범위 안에 있으면서 모든 자릿수가 서로 다른 정수 x를 찾는 문제입니다.

예를 들어 입력이 l = 211, r = 230이라면, 출력은 213이 됩니다. 211은 '1'이 두 번 나타나므로 조건을 만족하지 않지만, 213은 세 자릿수(2, 1, 3)가 모두 고유하기 때문입니다.

문제 해결 접근 방식

이 문제는 브루트포스(brute-force) 방식으로 간단하게 해결할 수 있습니다.

• l부터 r까지 모든 수를 하나씩 차례대로 확인합니다.
• 각 수를 문자열로 변환한 뒤, 각 자릿수를 집합(set)에 삽입합니다.
• 집합은 중복을 허용하지 않으므로, 집합의 크기와 문자열 길이가 같다면 해당 수의 자릿수가 모두 고유하다는 의미입니다.
• 조건을 만족하는 첫 번째 수를 찾으면 즉시 반환하고, 범위 전체를 탐색했는데도 없다면 "-1"을 반환합니다.

알고리즘 의사 코드

for initialize k := l, when k <= r, update (increase k by 1), do:
    h := convert k to string
    Define one set s
    for initialize i := 0, when i < size of h, update (increase i by 1), do:
        insert h[i] into s
    if size of s is same as size of h, then:
        return h
return "-1"

C++ 구현 예제

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

string solve(int l, int r) {
    for (int k = l; k <= r; k++) {
        string h = to_string(k);
        set<char> s;
        for (int i = 0; i < h.size(); i++)
            s.insert(h[i]);
        if (s.size() == h.size()) {
            return h;
        }
    }
    return "-1";
}
int main() {
    int l = 211;
    int r = 230;
    cout << solve(l, r) << endl;
}

실행 결과

입력

211, 230

출력

213

시간 복잡도 분석

범위의 크기를 n = r - l + 1이라 하고, 각 숫자의 최대 자릿수를 d라고 할 때 시간 복잡도는 O(n × d)입니다. 각 숫자마다 자릿수를 한 번씩 순회하며 집합에 삽입하기 때문입니다. 일반적인 문제 제약 조건(예: l, r ≤ 10⁵)에서는 충분히 빠르게 동작하지만, 범위가 매우 넓어지면 자릿수 마스크(bitmask)를 활용한 더 효율적인 접근을 고려할 수 있습니다.