백준 2992번 [크면서 작은 수](C++) -yes6686- 티스토리

백준 문제 풀이: 2992 (크면서 작은 수)

---

문제 링크: https://www.acmicpc.net/problem/2992

문제 설명:

주어진 숫자를 구성하는 모든 순열 중, 주어진 숫자보다 **크면서 작은 수**를 찾아 출력하는 문제입니다. 해당 조건을 만족하는 수가 없다면 **0**을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int visited[6]; // 방문 여부 확인 배열
string str;     // 입력 숫자
vector v; // 순열 저장 벡터

// DFS를 이용해 순열 생성
void dfs(string s, int depth) {
    if (depth == str.size()) {
        v.push_back(s); // 모든 자릿수를 사용한 경우 순열 저장
        return;
    }

    for (int i = 0; i < str.size(); i++) {
        if (!visited[i]) {
            visited[i] = 1;
            dfs(s + str[i], depth + 1);
            visited[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> str;

    // 모든 순열 생성
    dfs("", 0);

    // 생성된 순열을 정렬
    sort(v.begin(), v.end());

    // 주어진 수보다 큰 첫 번째 수 출력
    for (const string& s : v) {
        if (s > str) {
            cout << s << '\n';
            return 0;
        }
    }

    // 만족하는 수가 없으면 0 출력
    cout << 0 << '\n';
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: DFS를 사용하여 주어진 숫자를 구성하는 모든 순열을 생성한 후, 오름차순으로 정렬하고 조건에 맞는 수를 찾습니다.
• 구현 세부사항:
  • dfs(): 현재 문자열 s에 숫자를 하나씩 추가하면서 모든 가능한 순열을 생성합니다.
  • sort(): 생성된 모든 순열을 정렬합니다.
  • 정렬된 순열 중에서 입력 숫자보다 **큰 첫 번째 수**를 찾아 출력합니다.
  • 조건에 맞는 수가 없다면 **0**을 출력합니다.
• 시간 복잡도 분석:
  • 주어진 숫자의 길이를 n이라 하면, 순열 생성의 시간 복잡도는 O(n!)입니다.
  • 정렬의 시간 복잡도는 O(n! log n!)입니다.
  • 입력 숫자의 길이가 최대 5이므로 O(n!)은 충분히 해결 가능합니다.

---

결과

주어진 숫자보다 큰 순열 중 가장 작은 값을 정확히 출력합니다.

• 입력 예시:

  123

• 출력 예시:

  132

• 입력 예시:

  321

• 출력 예시:

  0

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!