[코딩테스트] 브루트 포스(순열)
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
- 순열 : 임의의 수열을 다른 순서로 섞는 연산
- A = [1,5,6]인 경우[1,5,6], [1,6,5], [5,1,6], [5,6,1], [6,1,5], [6,5,1]
- 크기 N인 수열의 순열 N!개
- 브루투포스 문제인데 순서가 중요한 경우(N가지의 순서 바꾸는 것만 가능할때)
- 첫 순열을 만든다. : 오름차순(비내림차순 정렬)
- 위를 이용해 다음 순열을 구한다. (반복)
- 마지막 순열 : 내림차순(비오름차순 정렬)
다음 순열 (10972번)
https://www.acmicpc.net/problem/10972
- 다음 순열은 C++일 경우 next_permutation, prev_permutation 이용, 자바는 직접 구현, 파이썬은 itertools
- 이 순열이 무엇으로 시작하는 마지막 순열인지 알아보고 첫순열 만들어주기
1324
1342 : 13으로 시작하는 마지막 순열
1423 : 14로 시작하는 첫 순열
- A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다 O(N)
마지막순열이 가장 긴 걸 찾아주기 (ex. A=7236541 은 723으로 시작하는 마지막 순열) : 어디까지 내림차순인지 확인하기 - j≥i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다 O(N)
마지막순열은 내림차순이니 j는 가장 오른쪽의 수이기 때문에 가장 큰 j라는 표현을 사용함, 7236541 이면 3보다 크고 가장 작은 수(4)를 찾기 - A[i-1]과 A[j]를 swap 한다 O(1)
ex) 7236541 -> 7246531 - A[i]부터 순열을 뒤집는다 O(N)
ex) 7246531 -> 7241356 완성!
- 각각 시간복잡도를 더해주면 다음순열을 구하는 데 걸리는 시간 O(N), 모든 순열은 O(N x N!)
- 함수에 주어진 순열을 변경할거고 리턴값 true : 다음순열 있음 / false : 다음 순열 없음
-
c++ 예
bool next_permutation(int *a, int n){ //1단계 int i = n-1; while(n>0 && a[i-1] >= a[i]) i-=1; // 1단계 if(i<=0) return false; //마지막순열 //2단계 int j = n-1; while(a[j] <= a[i-1]) j-=1; //3단계 swap(a[i-1], a[j]); //4단계 j = n-1; while(i<j){ swap(a[i], a[j]); i += 1; j -= 1; } return true; } -
java 코드
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++) { a[i] = sc.nextInt(); } if(next_permutation(a)) { for(int i=0; i<n; i++) { System.out.print(a[i] + " "); } System.out.println(); } else { System.out.println("-1"); } } public static boolean next_permutation(int[] a) { //1단계 int i = a.length-1; while(i>0 && a[i-1] >= a[i]) i-=1; if(i<=0) return false; //2단계 int j = a.length-1; while(a[j]<=a[i-1]) j-=1; //3단계 int temp = a[i-1]; a[i-1] = a[j]; a[j] = temp; //4단계 j = a.length-1; while(i<j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i += 1; j -= 1; } return true; } }
이전순열(10973번)
https://www.acmicpc.net/problem/10973
풀이
- 다음 순열을 하는 것들을 모두 반대로
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
if(prev_permutation(a)) {
for(int i=0; i<n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
} else {
System.out.println("-1");
}
}
public static boolean prev_permutation(int[] a) {
//1단계
int i = a.length-1;
while(i>0 && a[i-1] <= a[i])
i-=1;
if(i<=0)
return false;
//2단계
int j = a.length-1;
while(a[j]>=a[i-1])
j-=1;
//3단계
int temp = a[i-1];
a[i-1] = a[j];
a[j] = temp;
//4단계
j = a.length-1;
while(i<j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
}
모든순열(10974번)
https://www.acmicpc.net/problem/10973
풀이
- 다음 순열을 구하는 함수가 false 리턴할 때까지 계속 반복
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i=0; i<n; i++) {
a[i] = i+1;
}
for(int i=0; i<n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
while(next_permutation(a)) {
for(int i=0; i<n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
public static boolean next_permutation(int[] a) {
int i = a.length-1;
while(i>0 && a[i-1] >= a[i])
i-=1;
if(i<=0)
return false;
int j = a.length-1;
while(a[j]<=a[i-1])
j-=1;
int temp = a[i-1];
a[i-1] = a[j];
a[j] = temp;
j = a.length-1;
while(i<j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i += 1;
j -= 1;
}
return true;
}
}
- 이렇게도 통과되긴 하는데 do while 쓰는게 더 좋은 거 같다!!
- 10! = 3900만이라 safe 인데 11! 만 가도 4억이 넘음, 그래서 순서 이용하는 브루투포스는 보통 N≤10 이다.
댓글남기기