프로그래머스 - 단체사진 찍기 문제 (자바)

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

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

모든 경우의 수를 구하고 그 경우 중에서 조건을 만족하는 경우를 카운트하는 방식으로 해결할수있다.

 

주의점

1. 전역변수 초기화

하나의 테스트 케이스에서 여러 값들을 넣어보는 테스트를 진행하기 때문에 전역변수로 설정하면 내부 로직에서 초기화 작업이 필수이다. 바로 아래 코드에서는 int cnt 값을 static으로 설정한 뒤 solution 메서드 안에서 0으로 초기화 하고 있다.

 

2. 방문여부를 처리

멤버 각각의 방문 처리를 해야하는데 알파벳이 순서대로 있는 것이 아니기 때문에 신경 써야함.

바로 및 코드에서는 'A'로 뺏을때 나올수 있는 최대가 19 이길래 20 배열로 해결함.

 

3. 간격 값

두 멤버의 인덱스를 구하고 해당 인덱스의 차이와 이를 조건의 숫자와 비교할 때 조건의 숫자를 + 1해서 비교해야한다. 

만약 조건이 =0 이라면 딱붙어야함으로 인덱스의 차이가 1이어야한다. 다른 조건들에도 동일하므로 초기에 조건의 숫자에 +1을 미리 해놓고 비교하는게 편한다.

// 프로그래머스 단체사진 찍기 문제
class Solution {
    static int cnt;
    static public int solution(int n, String[] data) {
        char[] members = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
        boolean[] visited = new boolean[20];
        cnt = 0;
        permutation(members, "", visited, data);
        return cnt;
    }

    static void permutation(char[] members, String temp, boolean[] visited, String[] data) {
        if(temp.length() == 8) {
            checkPosition(temp, data);
            return;
        }

        for(int i = 0; i < members.length; i++) {
            if(!visited[(members[i] - 'A')]) {
                visited[(members[i] - 'A')] = true;
                permutation(members, temp + members[i], visited, data);
                visited[(members[i] - 'A')] = false;
            }
        }
    }

    static void checkPosition(String line, String[] data) {
        for (String datum : data) {
            char sign = datum.charAt(3);
            int value = datum.charAt(4) - '0' + 1;

            int firstIdx = 0;
            int secondIdx = 0;
            for(int i = 0; i < line.length(); i++) {
                if(line.charAt(i) == datum.charAt(0)) {
                    firstIdx = i;
                }

                if(line.charAt(i) == datum.charAt(2)) {
                    secondIdx = i;
                }
            }

            int distance = Math.abs(firstIdx - secondIdx);
            if((sign == '=' && distance != value)
                    || (sign == '>' && distance <= value)
                    || (sign == '<' && distance >= value)) {
                return;
            }
        }
        cnt++;
    }
}