[프로그래머스] Lv2. 단체사진 찍기 (Java)

프로그래머스

 

단체사진 찍기

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 

그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다.

네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다.

사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해 보게 되었다.

각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

 

입력 형식

n: 조건의 개수	data: 조건	answer
2	["N~F=0", "R~T>2"]	3648
2	["M~C<2", "M~C>1"]	0

data의 원소는 다섯 글자(0~4번)로 구성된 문자열입니다.

• 0번, 2번째 글자는 다음 8개로 프렌즈입니다. {A, C, F, J, M, N, R, T}
• 1번째 글자는 항상 ~입니다.
• 3번째 글자는 다음 3개 중 하나입니다. {=, <, >}
• 4번째 글자는 0 이상 6 이하의 정수의 문자형이며, 간격을 의미합니다. 이때 간격은 두 프렌즈 사이에 있는 프렌즈 수입니다.

 

 

*** 주의!!! ***

만약 예시를 모두 통과하고 코드를 잘 짠 것 같은데 제출 코드에서 실패가 뜬다면?

static으로 선언한 전역변수를 public int solution 안에 초기화를 해주는 식으로 고쳐봅시다!

원래 다른 문제들은 제출 테스트케이스가 여러 개로 되어 있는데 이 문제는 1개에서 여러 번 돌면서 코드를 검사하나 봅니다.

그래서 전역변수를 solution함수 안에 새로 초기화를 해주는 식으로 제출해야 통과가 됩니다!

---

접근 과정

1. 프렌즈를 한 명씩 나열하는 과정은 일단 1명을 먼저 배치하고, 이미 배치한 프렌즈가 아닌 프렌즈를 하나 또 배치하고,...

    이런 식으로 배치가 되기 때문에 DFS(깊이-우선 탐색)을 사용해 풀이하였습니다.

DFS를 사용하기 위해서는 시간초과가 걸리는 건 아닌지에 대해 확인을 해봐야 합니다.
프렌즈가 항상 총 8명으로 DFS로 프렌즈들을 나열한다면 경우의 수는 8! = 40320입니다.
또 프렌즈를 모두 배치했을 때 data []에 들어있는 조건들을 모두 다 확인해 줘야 하기 때문에 배치마다 data의 길이(1 ≤ n ≤ 100)만큼 확인을 해줘야 합니다.
따라서 큰 알고리즘을 위주로만 생각했을 때, 시간초과(약 1억)가 걸리지 않을 것이라고 판단되어서 DFS를 이용했습니다.

 

2. DFS 탐색을 하며 프렌즈를 한 명씩 String에 추가하면서 배치합니다.

    프렌즈는 char [] 형이기 때문에 한 명씩 받아와서 +=로 String에 추가해 줍니다.

String position = ""; // 프렌즈 배치 위치
char[] friends = {'A','C','F','J','M','N','R','T'}; // 프렌즈

// friends를 한명씩 가져와서 배치에 추가시키기.
for(int i=0;i<8;i++){
	position+=friends[i]; // "ACF" + 'J'
}

 

3. DFS 탐색을 계속 이어나가다가 모든 프렌즈(8)를 배치하면 주어진 조건에 맞는지 검사합니다.

    이 검사를 위해 따로 conditionSatisfied 함수를 만들어줍니다.

 -> fDistance (query) qDistance 가 맞는지 확인해서 data의 모든 조건들을 만족할 때만 cnt를 더해줍니다.

 

---

전체 코드

class Solution {
    static char[] friends = {'A','C','F','J','M','N','R','T'}; //프렌즈 이름
    static boolean[] visited = new boolean[8]; // 프렌즈를 배치했는지 확인.
    static int cnt; //경우의 수
    public int solution(int n, String[] data) {
        
        cnt=0; //경우의 수 초기화 -> 전역변수를 안에서 초기화 해야 오류 안남.
        
        dfs("",data);
        
        return cnt;
    }
    //프렌즈들을 position 순서로 배치할 경우의 수
    void dfs(String position, String[] data){
        
        if(position.length()==8){ // 8명을 모두 배치했다면 조건(data)에 맞는지 확인
            if(conditionSatisfied(position,data)) cnt++; //조건을 모두 만족하면 cnt+1
            return;
        }
        
        for(int i=0;i<8;i++){ // 프렌즈 8명 중 배치 안된 프렌즈 -> 배치
            if(!visited[i]){
                visited[i]=true; // i번째 프렌즈 배치.
                dfs(position+friends[i],data); // ex) "ACF" + 'J'
                visited[i]=false; //i번째 프렌즈 배치 해제.
            }
        }
    }
    // 프렌즈를 position 순서로 세울 때, data 조건을 모두 만족하는지 확인.
    boolean conditionSatisfied(String position, String[] data){
        
        for(int i=0;i<data.length;i++){
            
            char f1=data[i].charAt(0); // 프렌즈 1 이름
            char f2 = data[i].charAt(2); //프렌즈 2 이름
            
            char query = data[i].charAt(3); //조건의 부호 {>, =, <}
            int qDistance = Integer.parseInt(data[i].charAt(4)+""); // 조건 dist.
            
            int f1Position=position.indexOf(f1+""); //position에서 f1의 위치
            int f2Position=position.indexOf(f2+""); //f2 위치
            
            int fDistance = Math.abs(f1Position-f2Position)-1; //f1~f2의 간격
            
            //아래의 세 조건 중 하나라도 만족하지 않는다면 return false.
            if(query=='>' && fDistance<=qDistance) return false; //query를 만족하지 않는 경우.
            
            else if(query=='=' && fDistance!=qDistance) return false;
                
            else if(query=='<' && fDistance>=qDistance) return false;
                
        }
        return true; //주어진 모든 조건(data)를 만족하면 true 반환.
    }
}