단체사진 찍기

 

시간이 좀 많이 걸렸는데 괜찮나..?

 

---

 

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

 

---

 

Problem

8명이 사진을 찍는데, 모든 경우의 수 중에서 data 에 주어진 조건이 모두 성립하는 경우의 수는 총 몇 가지가 있느냐 물어보는 문제이다.

 

주요 포인트는 다음과 같다.

 

1. 8명이 전부 사진에 담겨야 한다.
   (7명, 6명.. 의 경우의 수는 존재할 수 없고, 중복되는 사람이 있을 수 없다)
2. 조건식 (data) 은 항상 5글자로, 다음과 같은 규칙을 따른다.
   (간격의 값은 최대 6이므로 조건식은 5글자를 벗어날 수 없음)

 

주의할 점은 바로 옆 자리로 붙어 있는 두 사람의 간격은 1이 아니라 0이라는 점이다.

그러니까 [A, B] 라면 B 와 A 의 간격은 B (index 1) - A (index 0) = 1 가 아니고, 0 이다. 

즉, 두 사람의 간격을 계산하려면 [ { ( 두 사람의 index의 차이 ) 의 절댓값 } - 1 ] 으로 계산하여야 한다.

 
 
 

Idea

결과를 먼저 얘기하면, 8명의 사람이 있을 수 있는 경우의 수를 모두 만들어보고,

각각의 경우의 수가 조건을 통과하는지 확인하면 된다.

 

사진에 들어가야 하는 사람 수는 8명이고, 따라서 총 경우의 수는 8! = 40320 이 되며,

각 결과가 조건에 맞는지, 즉 40320 번의 검증을 해야 한다.

이는 검증 조건이 하나일 때만이고, 만약 검증 결과가 2번이면 8! * 2, 3번이면 8! * 3..

n번이면 8! * n 의 검증을 거쳐야 한다.

 

검증 횟수가 너무 많아지는 것 같아 마음에 들지 않아서 다른 분들의 정답도 찾아봤는데, 대체로 방식은 비슷한 것 같다.

추후 더 좋은 알고리즘을 생각해보기로 하고, 우선은 해당 방식으로 진행했다.

 

 

 

Solution

여러 방법이 있겠지만, 나의 경우 가장 직관적이고 간편한 dfs 를 통해

[ 전체 경우의 수 만들기 + 마지막 depth 에서 검증하기 ] 로 풀이했다.

 

dfs 로 전체 경우의 수를 만들고, 마지막 depth 에서 검증하는 플로우를 조금 더 직관적으로 표현하면,

 

 

이렇게 표현할 수 있다.

 

즉 문제의 경우 1 ~ 8 번 자리가 있으며, 8 번 자리까지 꽉 찼을 때 조건에 맞는지 검증한다고 보면 된다.

따라서 depth == 8 일 때 해당 경우의 수가 조건에 부합하는지 검증하는 check 메서드를 통과하면

전역 변수인 count 를 1씩 증가하도록 구현하였다.

 
 
 

Code (DFS)

dfs 로 재귀 함수를 만들어 전체 경우의 수를 만들고, 각각 검증하는 코드이다.

 

class Solution {
    
    // 최종 답이 될 전역 변수 (조건에 통과한 경우의 수)
    public int count = 0;
    
    // 사람 이름 배열 전역 변수
    public String[] names = {"A", "C", "F", "J", "M", "N", "R", "T"};
    
    // 전체 경우의 수를 만들고 검증할 dfs 메서드
    public void dfs(int depth, boolean[] visited, String[] picture, String[] data) {
        
        // 재귀 함수의 depth 가 전체 사람 수와 같아진다면, 현재 모든 사람을 담은 경우의 수를 만들었음을 뜻함
        // 해당 경우의 수가 조건에 부합하는지 check 메서드를 통해 검증하고, 통과했을 때만 count++
        if(depth == names.length && check(picture, data)) {
            count++;
            return;
        }
        
        // visited 배열을 통해, 해당 경우의 수에서 이전에 포함됐던 사람이 또다시 추가되는 것을 방지
        for(int i=0; i<names.length; i++) {
            
            // 만약 i 번째 사람이 지금 경우의 수에서 이전에 포함된 적 없다면
            if(!visited[i]) {
                
                // i 번째 사람이 다음 dfs 에서 포함되는 것을 방지하기 위해 visited 배열을 true 로 수정
                visited[i] = true;
                
                // i 번째 사람을 picture 의 현재 자리(depth) 에 포함시키고 다시 dfs
                picture[depth] = names[i];
                dfs(depth+1, visited, picture, data);
                
                // 다음 dfs 를 통과하고 나왔으므로, 다음 경우의 수를 위해 다시 visited 배열을 false 로 수정
                visited[i] = false;
            }
        }
    }
    
    // 해당 경우의 수가 모든 조건에 전부 부합하는지 검증하는 메서드
    public boolean check(String[] picture, String[] data) {
        
        // 코드 작성의 편의를 위해 String 배열을 합쳐서 하나의 문자열로 만들어줌
        String pictureString = String.join("", picture);
        
        // 개별 조건이 통과하는지 검증하며, 하나의 조건이라도 통과하지 못한다면 바로 return false
        for(String expression : data) {
            char[] exArr = expression.toCharArray();
            
            if(!calculate(
                pictureString.indexOf(exArr[0]),
                pictureString.indexOf(exArr[2]),
                exArr[3],
                Character.getNumericValue(exArr[4]))) {
                
                    return false;
            }
        }
        
        return true;
    }
    
    // 해당 경우의 수가 개별 조건에 부합하는지 검증하는 메서드
    public boolean calculate(int idx1, int idx2, char sign, int gap) {
        
        // 두 사람의 간격 == (index 차이 - 1) 를 계산
        int diff = Math.abs(idx1 - idx2) - 1;
        
        switch(sign) {
            case '=':
                return diff == gap;
            case '>':
                return diff > gap;
            case '<':
                return diff < gap;
        }
        
        return false;
    }
    
    public int solution(int n, String[] data) {
        boolean[] visited = new boolean[8];
        String[] picture = new String[8];
        
        dfs(0, visited, picture, data);
        
        return count;
    }
}

 

 

시간은 조금 오래 걸렸지만 무사히 통과하였다.

 
 

 

End

처음 문제만 보고 풀어볼 엄두가 안 나서 미뤄왔던 문제였는데, 의외로 간단한 알고리즘만으로 해결되었다.

하지만 전체 경우의 수를 모두 만들고 모두 검증하는 로직이라는 점에서 조금 아쉬운 점이 남는 코드..

이런 코드는 사람의 수나 조건의 수가 늘어날수록 지수적으로 시간이 증가할 것이므로 좋지 않은 코드라 볼 수 있겠다.

더 좋은 방법이 있을 것 같아 나중에 고민해보고 싶다.