2018년 8월 4일 카카오 코딩테스트 예선에 앞서서 예비 문제를 풀어보도록 하겠습니다.
이번에 풀어 볼 문제는 2번 단체사진 찍기 문제로 아래와 같습니다.
푸는 방식은 간단하면서도 살짝 어렵습니다.
기본적으로 8명의 카카오 프렌즈 친구들을 나열하는 문제이기 때문에 순열 문제로 접근할 수 있습니다.
예제 입력을 확인하자면 N~F=0은 N과 F가 나란히 (이웃하는) 서서 나열되는 경우입니다.
또한 R~T>2라는 것은 R과 T가 3이상 떨어져 있다는 것입니다.
이 두 조건을 만족하면서 8개의 알파벳을 나열하면 본 문제는 해결되는 것입니다.
따라서 알고리즘 회로를 생각해보면 아래와 같습니다.
1. 8개의 알파벳이 모두 나열될 때까지 Permutation 함수를 재귀로 돌립니다.
2. 8개의 알파벳이 모두 나열되어 하나의 문자열이 완성될 때 조건을 체크합니다.
3. 조건이 만족할 경우, 해당 문자열을 리스트에 넣어줍니다.
4. 조건에 만족하면서 이미 나열된 문자열을 담은 리스트의 사이즈를 반환합니다.
이 4개의 조건대로 코드를 정리하면 됩니다.
우선 Permutation 함수를 정의해보겠습니다.
private static void permutation(String str, int L, int F, String[] command) {
if (L == F) {
if (thePermuteCondition(str, command1) && thePermuteCondition(str, command2)) {
list.add(str);
}
} else {
for (int i = L; i <= F; i++) {
str = swap(str, L, i);
permutation(str, L + 1, F, command);
str = swap(str, L, i); // back-tracking
}
}
}
1번 조건을 코드 그대로 설명한 것입니다.
문자들을 나열하되, 8개의 문자들이 모두 나열되어 문자열이 될 수 있도록 하고,
그렇지 않을 경우는 계속해서 자리를 교환하며 문자들을 나열시킵니다. (재귀 방식)
swap 함수는 아래와 같습니다. 보통의 swap함수와 같으며, 조금 신경써야 할 부분은
문자열을 받은 것이기 때문에 char형으로 바꿔서 변형 시켜줘야 한다는 점입니다.
private static String swap(String str, int i, int j) {
char temp;
char[] charArray = str.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
다음은 입력으로 넣은 조건들을 체크할 함수를 만들어줍니다.
보통은 이러한 함수들은 boolean 형태로 만들어서 체크하도록 합니다.
private static boolean thePermuteCondition(String input, String command) {
// 같을 조건
if ((command.charAt(3) == '=')) {
if (Math.abs((input.indexOf(command.charAt(0)))
- input.indexOf(command.charAt(2))) == (Integer.parseInt(command.substring(4))) + 1) {
return true;
}
}
// 미만일 조건
if ((command.charAt(3) == '<')) {
if (Math.abs((input.indexOf(command.charAt(0))) - input.indexOf(command.charAt(2))) < (Integer
.parseInt(command.substring(4)))) {
return true;
}
}
// 초과일 조건
if ((command.charAt(3) == '>')) {
if (Math.abs((input.indexOf(command.charAt(0)))
- input.indexOf(command.charAt(2))) > (Integer.parseInt(command.substring(4))) + 1) {
return true;
}
}
return false;
}
}
입력으로 넣은 문자열에서 값들을 뽑아 내어 원래의 문자열의 인덱스를 찾아갑니다.
인덱스를 가지고 같을 경우, 초과일 경우, 미만일 경우로 나눠서 풀면 됩니다.
해당 조건이 만족할 경우 true를 반환하고 기본적으로는 false를 반환합니다.
이 조건을 가지고 8개의 알파벳이 모두 나열될 때 조건이 만족하는지 체크하면 됩니다.
이것이 3번 조건에 해당합니다.
전체 조건을 만족한 경우 리스트에 추가하여 최종적으로는
리스트의 사이즈를 반환하면 본 문제는 해결됩니다.
전체 코드는 다음과 같습니다.
package 카카오코딩테스트연습;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class 단체사진_찍기 {
private static Scanner scanner;
private static int n;
private static ArrayList<String> list;
private static Stack<String> commandStack;
public static void main(String[] args) {
// TODO Auto-generated method stub
scanner = new Scanner(System.in);
n = scanner.nextInt(); // 횟수
String[] command;
command = new String[n];
String kakaoFriends = "ACFJMNRT";
list = new ArrayList<>();
commandStack = new Stack<String>();
for (int k = 0; k < n; k++)
command[k] = scanner.next() + "";
permutation(kakaoFriends, 0, 7, command);
// 문자열 index가 0부터 시작해서 7까지이기 때문..!!
System.out.println(list.size());
}
private static String swap(String str, int i, int j) {
char temp;
char[] charArray = str.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
private static void permutation(String str, int L, int F, String[] command) {
commandStack.push(command[0]);
String command1 = commandStack.pop();
commandStack.push(command[1]);
String command2 = commandStack.pop();
if (L == F) {
if (thePermuteCondition(str, command1) && thePermuteCondition(str, command2)) {
list.add(str);
}
} else {
for (int i = L; i <= F; i++) {
str = swap(str, L, i);
permutation(str, L + 1, F, command);
str = swap(str, L, i); // Back-Tracking
}
}
}
private static boolean thePermuteCondition(String input, String command) {
// 같을 조건
if ((command.charAt(3) == '=')) {
if (Math.abs((input.indexOf(command.charAt(0)))
- input.indexOf(command.charAt(2))) == (Integer.parseInt(command.substring(4))) + 1) {
return true;
}
}
// 미만일 조건
if ((command.charAt(3) == '<')) {
if (Math.abs((input.indexOf(command.charAt(0))) - input.indexOf(command.charAt(2))) < (Integer
.parseInt(command.substring(4)))) {
return true;
}
}
// 초과일 조건
if ((command.charAt(3) == '>')) {
if (Math.abs((input.indexOf(command.charAt(0)))
- input.indexOf(command.charAt(2))) > (Integer.parseInt(command.substring(4))) + 1) {
return true;
}
}
return false;
}
}
감사합니다.
'Algorithm' 카테고리의 다른 글
| 기수변환 알고리즘 (0) | 2018.11.14 |
|---|---|
| 백트래킹 코드 정리 (0) | 2018.10.16 |
| BOJ_11066_파일합치기 (0) | 2018.07.29 |
| 팰린드롬 만들기 (0) | 2018.07.27 |
| BOJ_10942_팰린드롬? (0) | 2018.07.27 |
