5619 c++ - 세 번째

세번째 작은 수 찾는 프로그램. 우선 처음 접근을 next_permutation을 통해 찾으려고 했는데, 해당 함수는 1,1,1 과 같은 중복된 숫자에 대해서 순열을 찾지 않는다는 것을 깨달았습니다. 이는 모든 요소가 동일하기 때문에 사전 순으로 더 이상의 다른 순열이 존재할 수 없기 때문입니다. 

  int i = 0;
  do {
    if (i == 2) {
      cout << a[0] << a[1];
      break;
    }
    i++;
  } while (next_permutation(a.begin(), a.end()));

 

그래서 dfs로 변경해서 풀었는데, 갯수가 10^8개가 되면서 dfs로 전부 찾으려고 하니까 시간 초과가 났다.

생각해보니, 가장 작은 수 4개만 찾으면 세번째로 작은 수를 찾을 수 있을거라 판단하고 코드를 작성하여 해결했다.

 

정답 코드.

#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) {
    // for (auto s : sa) cout << s << " ";
    // cout << "\n";
    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;
}