https://www.acmicpc.net/problem/10974
10974번: 모든 순열
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
www.acmicpc.net
분류 : 순열
더보기
import java.io.*;
import java.math.*;
import java.util.*;
class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
char nextChar() {
return next().charAt(0);
}
}
public class Main
{
static StringBuilder sb = new StringBuilder();
public static PrintWriter out;
static int N;
public static void main(String[] args) throws IOException
{
MyScanner sc = new MyScanner();
N = sc.nextInt();
int[] arr = new int[N];
for(int i=0;i<N;i++)
{
arr[i] = i+1;
sb.append(i+1+" ");
}
sb.append("\n");
while(nextPermutation(arr)){}
System.out.println(sb.toString());
}
private static boolean nextPermutation(int[] arr)
{
int index1 = arr.length-1;
while(index1>0 && arr[index1-1]>=arr[index1]){
index1--;
}
if(index1<=0)
return false;
int index2 = arr.length-1;
while(arr[index2]<=arr[index1-1]){
index2--;
}
int tmp = arr[index1-1];
arr[index1-1]= arr[index2];
arr[index2] = tmp;
index2 = arr.length-1;
while(index1<index2){
tmp=arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
index1++;
index2--;
}
Print(arr);
return true;
}
private static void Print(int[] arr) {
for(int i=0;i<N;i++){
sb.append(arr[i]+" ");
}
sb.append("\n");
}
}
문제만 읽으면 정말 단순한 문제 모든 순열 만들어서 출력하는 문제..
C++에서는 nextPermutation 함수를 이용하면 쉽게 풀린다고 한다.
하지만 자바는 없기에 구글링 해가면서 배웠다..
코드는 http://java7ang.tistory.com/9 에서 주로 참조하였고 마이구미라는 분의 블로그 자료도 보며 코드를 수정했다.
공부가 많이 부족하구나 라는 생각이 자주 든다..
같은 맥락의 문제로는 "10819번 : 차이를 최대로"가 있다.
'PS' 카테고리의 다른 글
[BOJ]4179번 : Fire! (0) | 2017.03.31 |
---|---|
[BOJ]7569번 : 토마토 (0) | 2017.03.29 |
[BOJ]11657번 : 타임 머신 (0) | 2017.03.28 |
[BOJ]4195번 : 친구 네트워크 (0) | 2017.03.25 |
[BOJ]1976번 : 여행 가자 (0) | 2017.03.25 |