[Programmers] LV2. 단체사진 찍기

https://programmers.co.kr/learn/courses/30/lessons/1835

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

 

✔ 문제 조건

1. 모든 친구를 조건에 맞추어서 줄 세워야 한다.
2. 조건들은 data[] 배열의 원소들이다. 하나의 조건 data[i]에서
   1. data[i].charAt(0) 과 data[i].charAt(2)는 조건 당사자들이다.
   2. data[i].charAt(3) 은 {=, <. >}으로 각각 같음, 미만, 초과를 의미한다.
   3. data[i].charAt(4)는 조건 당사자들 사이에 유지해야 할 간격 수이다.

✔ 접근 과정

1. dfs로 친구들 한명씩 조건에 맞추면서 줄을 세운다. 이미 줄 세워진 친구들의 다음 자리에 모든 친구 경우들을 넣어보며 조건을 충족하는지 살펴본다. visit배열로 아직 줄 세우지 않은 친구들 중, 이미 줄 세워진 친구들과의 조건에 충족한다면 줄을 세우고 다음 dfs로 넘긴다. 이때 줄을 세웠다고 visit 배열에 표시한 후, dfs가 끝난 후 표시를 해제하며 백트래킹한다.
2. dfs로 줄을 세우다가 8명을 모두 줄 세웠으면 total변수를 증가시킨다.

 

✔ 주의할 점

1. Java에서 String 변수 + char 변수 연산은 불가능하다. char 변수를 String으로 변환해야 하기 때문에 번거롭다. 따라서 String변수에 반환형이 char인 charAt()으로 접근하지 않고 str.substring(beginindex, endindex)로 잘라서 사용했다.
2. 제출하니 답이 이상하게 나와서 보니까 전역변수 초기화를 매번 새로 해주어야 했다.

// 210620

class Solution_LV2_단체사진찍기 {
    static String[] data;
    static int total;
    static String[] friends = new String[] { "A", "C", "F", "J", "M", "N", "R", "T" };
    static boolean[] v;
    
    public int solution(int n, String[] inputData) {
        data = inputData;
        total = 0;
        v = new boolean[8];
        
        for (int i = 0; i < 8; i++) {
            v[i] = true;
            dfs(1, friends[i]);
            v[i] = false;
        }
        return total;
    }
    
    static void dfs(int depth, String curString) {
        if (depth >= 8) {
            //System.out.println(curString);
            ++total;
            return;
        }
        for (int i = 0; i < 8; i++) {
            if (!v[i] && isPossible(friends[i], curString)) {
                v[i] = true;
                dfs(depth + 1, curString + friends[i]);
                v[i] = false;
            }
        }
    }

    static boolean isPossible(String strA, String curString) {
        for (String d : data) {
            if (d.substring(0, 1).equals(strA)) { // 조건 당사자
                String strB = d.substring(2, 3);
                int diff = Integer.parseInt(d.substring(4));
                String condition = d.substring(3, 4);

                for (int i = 0; i < curString.length(); i++) {
                    String cur = curString.substring(i, i + 1);
                    if (cur.equals(strB)) {
                        int tmpDiff = (curString.length()-1) - i;
                        //System.out.println(tmpDiff + " " + strA + " " + cur);
                        if (condition.equals("=") && tmpDiff != diff) {
                            return false;
                        } else if(condition.equals(">") && !(tmpDiff > diff)) {
                            return false;
                        } else if(condition.equals("<") && !(tmpDiff < diff)) {
                            return false;
                        }
                    }
                }

            } else if (d.substring(2, 3).equals(strA)) { // 자신이 상대방
                String strB = d.substring(0, 1);
                int diff = Integer.parseInt(d.substring(4));
                String condition = d.substring(3, 4);

                for (int i = 0; i < curString.length(); i++) {
                    String cur = curString.substring(i, i + 1);
                    if (cur.equals(strB)) {
                        int tmpDiff = (curString.length()-1) - i;
                        //System.out.println(tmpDiff + " " + strA + " " + cur);
                        if (condition.equals("=") && tmpDiff != diff) {
                            return false;
                        } else if(condition.equals(">") && !(tmpDiff > diff)) {
                            return false;
                        } else if(condition.equals("<") && !(tmpDiff < diff)) {
                            return false;
                        }
                    }
                }
            } */
        }
        return true;
    }    
    
}