프로그래머스 level2 ) 단체사진 찍기
문제를 보고 순열로 풀어야겠다는 생각이 들었다.
정규식을 만들어서 그 패턴에 해당하는 순열의 수를 세었는데
테스트케이스에서는 빠르게 정답이 나왔는데
제출을 하니 시간초과
어디서 시간을 줄여야할지...
import java.io.IOException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Solution {
static int answer;
static String make_string(char[] arr, int r) {
StringBuilder result = new StringBuilder();
for(int i = 0; i < r; i++)
result.append(arr[i]);
return result.toString();
}
// 패턴이 들어갔는지 check
static boolean check_pattern(String[] regexs, String str) {
int true_count=0;
for(int i = 0; i < regexs.length; i++) {
Pattern pattern = Pattern.compile(regexs[i]);
Matcher matcher = pattern.matcher(str);
if(matcher.find())
true_count++;
}
return true_count==regexs.length;
}
// 정규식 만들기
static String[] make_pattern(char[][] ch) {
StringBuilder result;
String[] regexs = new String[ch.length];
for (int i = 0; i < ch.length; i++) {
result = new StringBuilder();
result.append("("+ch[i][0]+"|"+ch[i][1]+")("+"[A-Z]");
if (ch[i][2] == '=') {
result.append("{" + ch[i][3] + "," + ch[i][3] + "})");
} else if (ch[i][2] == '>') {
int num = Integer.parseInt(ch[i][3]+"")+1;
result.append("{" + num + ",6})");
}
else if (ch[i][2] == '<') {
int num = Integer.parseInt(ch[i][3]+"")-1;
result.append("{0," + num + "})");
}
result.append("("+ch[i][0]+"|"+ch[i][1]+")");
regexs[i]=result.toString();
}
return regexs;
}
static void per2(char[] arr, char[] output, boolean[] visited, int depth, int n, int r, String[] regexs) {
if (depth == r) {
String str = make_string(output, depth);
if(check_pattern(regexs, str))
answer++;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
per2(arr, output, visited, depth + 1, n, r, regexs);
visited[i] = false;
}
}
}
public int solution(int n, String[] data) {
boolean[] visited = new boolean[8];
char[] arr = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
char[] output = new char[8];
// A, C, F, J, M, N, R, T
// 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브
char[][] pattern = new char[data.length][4];
for (int i = 0; i < data.length; i++) {
String temp = data[i].replace("~", "");
pattern[i] = temp.toCharArray();
}
answer = 0;
per2(arr, output, visited, 0, 8, 8, make_pattern(pattern));
return answer;
}
}
모든 조합을 String으로 만들기 위해서 도는 for문 때문이지 않을까
static String make_string(char[] arr, int r) {
StringBuilder result = new StringBuilder();
for(int i = 0; i < r; i++)
result.append(arr[i]);
return result.toString();
}
정규식에 해당하는 순열만 string으로 바꾸고 싶어도
string으로 바꿔야 정규식에 해당하는지 알수있움 ㅜㅜㅜ
결국 정규식 말고 다른걸로 check해야함
다른 분들꺼 보고 조금씩 고쳐서 다시 풀었당
import java.io.IOException;
import java.util.HashMap;
public class Main {
static int answer;
static int[] ch;
public static boolean check(String[] data) {
int a, b, res;
char op;
for (String s : data) {
a = ch[map.get(s.charAt(0))];
b = ch[map.get(s.charAt(2))];
op = s.charAt(3);
res = s.charAt(4) - '0' + 1;
if (op == '=') {
if (Math.abs(a - b) != res)
return false;
} else if (op == '>') {
if (Math.abs(a - b) <= res)
return false;
} else {
if (Math.abs(a - b) >= res)
return false;
}
}
return true;
}
static void per2(char[] arr, char[] output, boolean[] visited, int depth, int n, int r, String[] data) {
if (depth == r) {
if (check(data))
answer++;
return;
}
for (int i = 0; i < n; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
ch[depth] = i;
per2(arr, output, visited, depth + 1, n, r, data);
visited[i] = false;
}
}
}
static HashMap<Character, Integer> map;
public static void main(String[] args) throws IOException {
int n = 2;
String[] data = { "N~F=0", "R~T>2" };
boolean[] visited = new boolean[8];
char[] arr = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
ch = new int[8];
char[] output = new char[8];
// A, C, F, J, M, N, R, T
// 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브
map = new HashMap<>();
map.put('A', 0);
map.put('C', 1);
map.put('F', 2);
map.put('J', 3);
map.put('M', 4);
map.put('N', 5);
map.put('R', 6);
map.put('T', 7);
answer = 0;
per2(arr, output, visited, 0, 8, 8, data);
System.out.println(answer);
}
}
map에 해당 알파벳과 알파벳 위치가 들어있는 인덱스가 value로 들어 있다.
ch={4, 3, 5, 7, 0, 6, 2, 1 요런 식으로 들어 있으면
'N'에 위치는 index=5에 들어있다.
N은 6번 자리에 위치에 있고,
F는 5번 자리에 위치에 있다.
둘의 거리를 계산할수있다.
Author And Source
이 문제에 관하여(프로그래머스 level2 ) 단체사진 찍기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yuiopre98/프로그래머스-level2-단체사진-찍기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)