[BOJ] 10972 다음 순열
7563 단어 bojsilver3permutation백준알고리즘기초boj
다음순열
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
bool next_permutation(vector<int> &arr,int n)
{
int i = n-1;
while(i>=0 && arr[i]<= arr[i-1])
{
i -= 1;
}
if(i <= 0){
return false;
}
int j = n-1;
while(arr[j] <= arr[i-1])
{
j-=1;
}
swap(arr[i-1],arr[j]);
sort(arr.begin()+i,arr.end());
return true;
}
int main()
{
int n;
cin>>n;
vector<int> arr(n);
for(int i=0 ; i < n ; i++)
{
cin >> arr[i];
}
if(next_permutation(arr,n))
{
for(int i=0;i<n;i++)
{
cout<<arr[i]<<' ';
}
}
else{
cout<<"-1";
}
}
풀이방법
사전순으로 다음으로 오는 순열을 구하는 문제
c++ STL을 사용하지 않고 문제를 풀어보았다.
ex) 1 2 4 3 이면 다음 순열은 1 3 2 4 이기 때문에
벡터 arr인덱스에서 arr[i] > arr[i-1] 인 부분을 찾고
i보다 큰 인덱스이며 arr[i-1] 보다 큰 j를 구한뒤 swap
그다음 arr[i] 부분부터 sort함수를 통해 오름차순으로 정리해주었다.
Author And Source
이 문제에 관하여([BOJ] 10972 다음 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@wjdals0507/BOJ-10972-다음-순열-q9ajdv95
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; bool next_permutation(vector<int> &arr,int n) { int i = n-1; while(i>=0 && arr[i]<= arr[i-1]) { i -= 1; } if(i <= 0){ return false; } int j = n-1; while(arr[j] <= arr[i-1]) { j-=1; } swap(arr[i-1],arr[j]); sort(arr.begin()+i,arr.end()); return true; } int main() { int n; cin>>n; vector<int> arr(n); for(int i=0 ; i < n ; i++) { cin >> arr[i]; } if(next_permutation(arr,n)) { for(int i=0;i<n;i++) { cout<<arr[i]<<' '; } } else{ cout<<"-1"; } }
풀이방법
사전순으로 다음으로 오는 순열을 구하는 문제
c++ STL을 사용하지 않고 문제를 풀어보았다.
ex) 1 2 4 3 이면 다음 순열은 1 3 2 4 이기 때문에
벡터 arr인덱스에서 arr[i] > arr[i-1] 인 부분을 찾고
i보다 큰 인덱스이며 arr[i-1] 보다 큰 j를 구한뒤 swap
그다음 arr[i] 부분부터 sort함수를 통해 오름차순으로 정리해주었다.
Author And Source
이 문제에 관하여([BOJ] 10972 다음 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@wjdals0507/BOJ-10972-다음-순열-q9ajdv95
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
사전순으로 다음으로 오는 순열을 구하는 문제
c++ STL을 사용하지 않고 문제를 풀어보았다.
ex) 1 2 4 3 이면 다음 순열은 1 3 2 4 이기 때문에
벡터 arr인덱스에서 arr[i] > arr[i-1] 인 부분을 찾고
i보다 큰 인덱스이며 arr[i-1] 보다 큰 j를 구한뒤 swap
그다음 arr[i] 부분부터 sort함수를 통해 오름차순으로 정리해주었다.
Author And Source
이 문제에 관하여([BOJ] 10972 다음 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wjdals0507/BOJ-10972-다음-순열-q9ajdv95저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)