문제
N개의 한 자리 수에서 두 자리를 뽑아 이어붙여 만들 수 있는 두 자리 수 중 세 번째로 작은 수를 구하라.
입력
숫자 개수 N과 각 한 자리 수가 주어진다.
출력
세 번째로 작은 두 자리 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 2 1 3 4 | 13 |
풀이
가장 작은 3~4개의 숫자로 모든 두 자리 순열을 생성하여 정렬한다.
- N개의 수를 정렬하여 가장 작은 3~4개만 선택한다
- 선택된 수에서 2개를 골라 순열(순서 있는 조합)을 생성한다
- 생성된 두 자리 수를 정렬하여 3번째를 출력한다
핵심 아이디어: 가장 작은 수들로만 조합하면 세 번째로 작은 수를 찾기에 충분하므로, 전체 순열 대신 소수의 수만 처리한다.
코드
#include <algorithm>
#include <iostream>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
vector<int> result;
int n, r = 0;
void dfs(vector<int> sa, vector<int> a, vector<bool> v)
{
if (sa.size() == 2)
{
string res = "";
for (auto s : sa)
res += to_string(s);
result.push_back(stoi(res));
r++;
return;
}
for (int i = 0; i < a.size(); i++)
{
if (v[i])
continue;
v[i] = true;
sa.push_back(a[i]);
dfs(sa, a, v);
sa.pop_back();
v[i] = false;
}
}
int main()
{
fastio;
cin >> n;
vector<int> a(n);
vector<int> p(3);
vector<int> sa;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a.begin(), a.end());
p[0] = a[0];
p[1] = a[1];
p[2] = a[2];
if (n > 3)
p.push_back(a[3]);
vector<bool> v(p.size(), false);
dfs(sa, p, v);
sort(result.begin(), result.end());
cout << result[2];
return 0;
}복잡도
- 시간: O(N log N)
- 공간: O(N)