코딩테스트/프로그래머스
[Java] 프로그래머스 - 단체사진 찍기 (2단계)
배똥회장
2022. 4. 1. 14:42
728x90
코딩 테스트 풀이 체크리스트 |
|
2시간 내에 풀었는가? | X |
본인의 실력으로 풀었는가? | O |
하지만 일하면서 했기 때문에 양심적으로 2시간 내라고 인정해주라.
코딩테스트 연습 - 단체사진 찍기
단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두
programmers.co.kr
import java.util.*;
class Solution {
int answer = 0;
int[] numArr;
String[][] strArr;
boolean[] check;
public int solution(int n, String[] data) {
String[] name = {"A", "C", "F", "J", "M", "N", "R", "T"};
String nameStr = "ACFJMNRT";
check = new boolean[8];
strArr = new String[n][4];
numArr = new int[n];
for (int i = 0; i < data.length; i++) {
String[] dataArr = data[i].split("");
numArr[i] = Integer.parseInt(dataArr[4]);
strArr[i] = Arrays.copyOf(dataArr, 4);
}
func(strArr, name, new StringBuilder());
return answer;
}
public void func(String[][] data, String[] name, StringBuilder sb) {
if (sb.length() == 8) {
answer++;
return;
}
for (int i = 0; i < 8; i++) {
if (check[i]) continue;
StringBuilder temp = new StringBuilder(sb);
temp.append(name[i]);
boolean value = true;
for (int j = 0; j < data.length; j++) {
if (!data[j][0].equals(name[i]) && !data[j][2].equals(name[i])) continue;
int a = temp.indexOf(data[j][0]);
int b = temp.indexOf(data[j][2]);
if (a == -1 || b == -1) continue;
int num = Math.abs(a - b) - 1;
if (data[j][3].equals("<")) {
if (num >= numArr[j]) {
value = false;
break;
}
} else if (data[j][3].equals(">")) {
if (num <= numArr[j]) {
value = false;
break;
}
} else {
if (num != numArr[j]) {
value = false;
break;
}
}
}
if (value) {
check[i] = true;
func(data, name, temp);
check[i] = false;
}
}
}
}
테스트 1 〉 | 통과 (550.30ms, 162MB) |
한 글자씩 추가할 때 조건들을 비교하면서 조건에 적합하면 다음으로 넘어가고 아니면 그냥 끝내는 것으로 만들었는데,
이게 가능했던게, 일단 경우의 수가 8!에 조건이 최대 100개니까 엄청 큰 숫자가 아니기 때문에
가능하겠다고 생각이 들어서 그냥 조건 전체를 돌리는 것으로 만들었음.
그리고 한 번 쓴 문자는 쓰지 않도록 boolean 배열로 체크했고,
조건에 맞는지 확인 하는 것은 어떻게 했냐면
for (int j = 0; j < data.length; j++) {
if (!data[j][0].equals(name[i]) && !data[j][2].equals(name[i])) continue;
int a = temp.indexOf(data[j][0]);
int b = temp.indexOf(data[j][2]);
if (a == -1 || b == -1) continue;
int num = Math.abs(a - b) - 1;
if (data[j][3].equals("<")) {
if (num >= numArr[j]) {
value = false;
break;
}
} else if (data[j][3].equals(">")) {
if (num <= numArr[j]) {
value = false;
break;
}
} else {
if (num != numArr[j]) {
value = false;
break;
}
}
}
만약에 추가할 문자가 조건식에 없다면 그냥 넘어가고
조건식에 있다면 일단 추가할 문자와 상대방 문자가 있을 것이다.
그것들의 위치를 구하는데 만약 둘 중 하나가 추가되지 않아서 indexOf에서 -1을 리턴한다면 그냥 넘어가고
그렇지 않으면 이제 각 위치와 조건식이 부합한지 확인하기 위해 if문을 돌린...
이런 식으로 작성을 했다.
더보기
이건 예전에 작성한 코드인데 비슷한듯 다른...
근데 시간복잡도는 지금 작성한 코드가 저 낮아서 실력 향상한 기분이다~~
import java.util.*;
class Solution {
ArrayList<String> list;
String[] word = new String[]{"A", "C", "F", "J", "M", "N", "R", "T"};
boolean[] check = new boolean[8];
String[][] con;
int[] con_num;
public int solution(int n, String[] data) {
int answer = 0;
Arrays.fill(check, true);
list = new ArrayList<>();
con = new String[data.length][3];
con_num = new int[data.length];
for (int i = 0; i < data.length; i++){
String[] temp = data[i].split("");
con[i][0] = temp[0];
con[i][1] = temp[2];
con[i][2] = temp[3];
con_num[i] = Integer.parseInt(temp[4]);
}
funk(0, new String[8]);
return list.size();
}
public void funk(int num, String[] data){
if (num == 8){
boolean value = true;
String temp = String.join("", data);
for (int i = 0; i < con.length; i++){
int fir = temp.indexOf(con[i][0]);
int sec = temp.indexOf(con[i][1]);
int mid = Math.abs(sec - fir) - 1;
if (con[i][2].equals("=")){
if (mid != con_num[i]){
value = false;
break;
}
continue;
}
if (con[i][2].equals(">")){
if (mid <= con_num[i]){
value = false;
break;
}
continue;
}
if (con[i][2].equals("<")){
if (mid >= con_num[i]){
value = false;
break;
}
continue;
}
}
if (value) list.add(temp);
return;
}
for (int i = 0; i < word.length; i++){
if (check[i] == false) continue;
check[i] = false;
data[num] = word[i];
funk(num+1, data);
check[i] = true;
}
}
}
테스트 1 〉 | 통과 (2762.87ms, 369MB) |
728x90