코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
완전탐색으로 하기에는 n의 수가 20이므로 무조건 시간초과가 날 수 밖에 없다. 따라서 한 자리씩 수를 정해주는 방식으로 구현해보았다. 예를 들어, 맨 첫 자리를 1이라고 쳤을 때의 나오는 경우의 수는 (N-1)!이다. 만약 이 수가 K보다 크면 첫 자리를 1이라고 두고 다음 자리의 숫자를 찾아야 한다. 하지만 K보다 작으면 (N-1)!의 값을 K에서 빼주고 첫 자리를 2로 둔 다음 다시 계산해줘야한다. 이와 같은 방식으로 모든 자리의 숫자를 정해줘야 한다.
#include <string>
#include <vector>
using namespace std;
string num = "";
bool arr[21];
long long K;
int N;
long long factorial(int n) {
long long result = 1;
for (int i = 1; i <= n; ++i) {
result = result * i;
}
return result;
}
void rec(int dep) {
if (dep == N+1)
return;
for (int i = 1; i <= N; i++) {
if (arr[i])
continue;
long long val = factorial(N - dep);
if (val < K) {
K -= val;
}
else {
num += i + '0';
arr[i] = true;
rec(dep + 1);
}
}
}
vector<int> solution(int n, long long k) {
vector<int> answer;
K = k;
N = n;
rec(1);
for (int i = 0; i < num.size(); i++) {
answer.push_back(num[i]-'0');
}
return answer;
}
'코딩테스트 > C++' 카테고리의 다른 글
[프로그래머스 Level 2] 리코쳇 로봇(C++) (0) | 2024.05.08 |
---|---|
[ 백준 BOJ ] 1915번 - 가장 큰 정사각형 (C++) (0) | 2024.05.06 |
[프로그래머스 Level 2] 시소 짝꿍(C++) (0) | 2024.05.03 |
[프로그래머스 Level 2] 두 큐 합 같게 만들기(C++) (0) | 2024.05.03 |
stack 활용법 (0) | 2024.04.25 |