강의로 돌아가기
유병호

효율성 검사에서 시간초과 되는 이유를 알려주세요

include string
include vector
include algorithm

using namespace std;

vector<int> solution(int n, long long k) {
    vector<int> answer(n,0);

    for (int i = 0; i < answer.size(); ++i) {
        answer[i] = i+1;
    }

    for (int i = 0; i < k-1; ++i) {
        next_permutation(answer.begin(), answer.end());
    }
    for (int i = 0; i < answer.size(); ++i) {
        cout << answer[i];
    }

    return answer;
}

코드 구현한건데 시간초과 되는 이유 알려주시면 감사하겠습니다.

1 개의 답변
황규승

일일히 permutation 구하는건 O(n!) 이라서 testcase가 20일 경우엔 느립니다.

첫 번째 사람이 누군지는 쉽게 구할 수 있지 않을까요?

++) 재귀 함수 사용하면 c++ 기준으로 모든 테스트 0.01초 이내로 통과합니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.