글 읽기 - 다음 순열 사용 시 질문

djgjdgjd 6년 전 0

아래 코드로 제출하면 틀렸다고 나오는데 str에 문자열을 입력받은 뒤 sort한 후 제출하면 정답으로 나옵니다.

printf 찍어보면 sort하기 전에는 0번째가 아닌 1번째 인덱스부터 섞여서 나오는데 정렬한 후 찍어보면 0번째 인덱스부터 섞여서 나옵니다.

왜 next_permutation 사용하기 전에 정렬을 안하면 0번째가 아닌 1번째 인덱스부터 섞여서 나오나요?

#include <cstdio>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

int n, m, sum = 0, cnt = 0;
string str = "";
bool flag = true;

int main()
{
    cin>>str;
    //sort(str.begin(), str.end());
    
    do{
        flag = true;
        
        for(int i=1;i<str.length()-1;i++)
        {
            if(str[i-1] == str[i] || str[i] == str[i+1])
            {
                flag = false;
                break;
            }
        }
        
        if(flag)
            cnt++;
    }while(next_permutation(str.begin(), str.end()));
           
           cout<<cnt<<'\n';
    
    return 0;
}

solveit 6년 전 1

정렬을 안하면 주어진 str가 k번째 순열일때 1~k-1 번째 순열은 체크를 안하니까 오답을 내는겁니다.

djgjdgjd 6년 전 0

아ㅋㅋ 무슨말인지 알겠네요 감사ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다음 순열 사용 시 질문

djgjdgjd 6년 전 0

solveit 6년 전 1

djgjdgjd 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말