-----------------------------------------------------------------------------------------------------------------------------------------------------------------
문제 접근 순서
1. 해당 문제를 처음 볼 때 이해가 잘 안되었다. 감소하는 수?
천천히 문제를 이해해 보니 각 자리수의 가장 맨 앞에서 오름차순으로 내려가는 987654321 이렇게 형태를 갖춰야 하는것이
감소하는 수의 정의 이다.
2. 해당 문제 접근 방법으로는 첫 번째 string을 이용하여 모든 자리수를 구분하여 비교하는 방법이다.
이 방법은 965821의 경우 965까지 가서 8에서 돌아와야하는 백트래킹으로 효율적인 방법처럼 보이지만,
965까지 가야 한다는 것이 비효율적이라는 점도 있다.
3. 따라서 대안으로 DFS 구조로 각 자리수가 생길때 마다 비교를 통해 앞 뒤만 비교할 수 있도록 하여 더욱 효율적으로 감소하는 수를 찾기로 했다.
4. 감소하는 수는 총 10자리수가 한계이며 0~9까지 각 자리수마다 들어가면 된다는 것을 알면 된다.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
map<int, long long> m_map;
vector<long long> m_vec;
// cur: 현재까지 만든 감소하는 수
// lastDigit: 다음에 붙일 수 있는 최대 숫자(항상 lastDigit보다 작은 것만 붙임)
void DFS(long long cur, int lastDigit)
{
m_vec.push_back(cur);
// 다음 자리는 반드시 더 작은 숫자만 가능
for (int d = 0; d < lastDigit; d++)
{
DFS(cur * 10 + d, d);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int i_inputDecreaseNum = 0;
cin >> i_inputDecreaseNum;
// 0~9부터 시작해서 모든 감소하는 수 생성
for (int d = 0; d <= 9; d++)
DFS(d, d);
sort(m_vec.begin(), m_vec.end());
m_vec.erase(unique(m_vec.begin(), m_vec.end()), m_vec.end()); // 안전용(중복 거의 없음)
// map에 (인덱스 -> 값) 저장
int iCurrentCount = 0;
for (long long x : m_vec)
{
m_map.emplace(iCurrentCount, x);
iCurrentCount++;
}
// 출력 로직
if (m_map.find(i_inputDecreaseNum) == m_map.end())
cout << -1;
else
cout << m_map[i_inputDecreaseNum];
return 0;
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
다시 푼 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> g_vec;
void DFS(int _Number,long long _iCurrentNumber)
{
g_vec.push_back(_iCurrentNumber);
for(int i=0; i< _Number; i++)
{
DFS(i,_iCurrentNumber * 10 + i);
}
}
int main()
{
int i_input;
int index = 1;
cin >> i_input;
for (int i = 0; i <= 9; i++)
{
DFS(i, i);
}
sort(g_vec.begin(), g_vec.end());
if (i_input >= g_vec.size())
cout << -1;
else
cout << g_vec[i_input];
return 0;
}