1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
출력
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
예제 입력 1
| 4 1 2 3 4 |
예제 출력 1
| 1 2 4 3 |
예제 입력 2
| 5 5 4 3 2 1 |
예제 출력 2
| -1 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int compare(const void *x,const void *y)
{
return *(int *)x>*(int *)y?1:*(int *)x==*(int *)y?0:-1;
}
int main(void)
{
int N, *permutation=NULL, index, *to_change=NULL, last;
scanf("%d", &N);
permutation=(int *)malloc(N*sizeof(int));
for(int i=0;i<N;i++)
scanf("%d", &permutation[i]);
index=N-2;
while(index>=0 && permutation[index]>permutation[index+1])
index--;
if(index<0 || N==1)
{
printf("-1\n");
free(permutation);
return 0;
}
to_change=(int *)malloc((N-index)*sizeof(int));
for(int i=index;i<N;i++)
to_change[i-index]=permutation[i];
qsort((void *)to_change,(size_t)N-index,sizeof(int),compare);
last=N-index-1;
for(int i=index;i<N;i++)
if(to_change[i-index]>permutation[index])
last=to_change[i-index]<to_change[last]?i-index:last;
int temp=to_change[last];
for(int i=last;i>0;i--)
to_change[i]=to_change[i-1];
to_change[0]=temp;
for(int i=index;i<N;i++)
permutation[i]=to_change[i-index];
for(int i=0;i<N;i++)
printf("%d ", permutation[i]);
printf("\n");
free(permutation);
free(to_change);
return 0;
}더보기
Solution
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
StringTokenizer st;
int N=Integer.parseInt(br.readLine());
int[] permutation=new int[N];
st=new StringTokenizer(br.readLine());
for(int i=0;i<N;i++)
permutation[i]=Integer.parseInt(st.nextToken());
int index=N-2;
while(index>=0 && permutation[index]>permutation[index+1])
index--;
if(index<0 || N==1) {
System.out.println(-1);
return;
}
int[] to_change=new int[N-index];
for(int i=index;i<N;i++)
to_change[i-index]=permutation[i];
Arrays.sort(to_change);
int last=N-index-1;
for(int i=index;i<N;i++)
if(to_change[i-index]>permutation[index])
last=to_change[i-index]<to_change[last]?i-index:last;
int temp=to_change[last];
for(int i=last;i>0;i--)
to_change[i]=to_change[i-1];
to_change[0]=temp;
for(int i=index;i<N;i++)
permutation[i]=to_change[i-index];
for(int i=0;i<N;i++)
sb.append(permutation[i]+" ");
System.out.println(sb.toString());
}
}
728x90
'백준 알고리즘' 카테고리의 다른 글
| <백준 알고리즘> 1182번: 부분수열의 합 (0) | 2023.02.06 |
|---|---|
| <백준 알고리즘> 24511번: queuestack (0) | 2023.02.05 |
| <백준 알고리즘> 10799번: 쇠막대기 (0) | 2023.02.04 |
| <백준 알고리즘> 14370번: 전화번호 수수께끼 (Large) (0) | 2023.02.03 |
| <백준 알고리즘> 14369번: 전화번호 수수께끼 (Small) (0) | 2023.02.03 |
