[Java] 프로그래머스 - 단체사진 찍기 (2단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	X
본인의 실력으로 풀었는가?	O

하지만 일하면서 했기 때문에 양심적으로 2시간 내라고 인정해주라.

 

코딩테스트 연습 - 단체사진 찍기

 

 

 

 

 

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)