[프로그래머스 Level.2] 단체사진 찍기 (2017 카카오코드 본선) (Java)

문제 링크

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

프로그래머스

 

 

 

코딩테스트 연습 > 2017 카카오코드 본선 > 단체사진 찍기

 

 

문제 설명

 

 

단체사진 찍기

 

 

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다.

즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다.

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

사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

 

 

입력 형식

 

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다.

 

제한조건은 아래와 같다.

• 1 <= n <= 100
• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

 

 

출력 형식

 

모든 조건을 만족하는 경우의 수를 리턴한다.

 

 

예제 입출력

n	data	answer
2	["N~F=0", "R~T>2"]	3648
2	["M~C<2", "C~M>1"]	0

 

 

예제에 대한 설명

 

첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.

두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"};
    int answer = 0;
    
    public int solution(int n, String[] data) {
        boolean[] visited = new boolean[friends.length];
        
        dfs("", visited, data);
        
        return answer;
    }
    
    public void dfs(String line, boolean[] visited, String[] data) {
        if(line.length() == 8 && reqCheck(line, data)) {
            answer++;
            return;
        }
        
        for(int i=0; i<friends.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(line + friends[i], visited, data);
                visited[i] = false;
            }
        }
    }
    
    public boolean reqCheck(String line, String[] data) {
        for(int i=0; i<data.length; i++) {
            int position1 = line.indexOf(data[i].charAt(0));
            int position2 = line.indexOf(data[i].charAt(2));
            char operator =  data[i].charAt(3);
            int index = data[i].charAt(4) - '0';
            
            if(operator == '>') {
                if(!(Math.abs(position1 - position2) > index + 1)) return false;
            } else if(operator == '<') {
                if(!(Math.abs(position1 - position2) < index + 1)) return false;
            } else {
                if(!(Math.abs(position1 - position2) == index + 1)) return false;
            }
        }
        
        return true;
    }
    
}

 

풀이

1. 카카오프렌즈를 나타내는 String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"}를 만들어 완전탐색 dfs()를 이용하여 카카오프렌즈 모두를 이용한 모든 조합을 만들어 주어진 조건 data에 맞는지 확인하고 카운팅하면 된다.
2. 크기가 8인 String 배열 friends를 만들고 "A", "C", "F", "J", "M", "N", "R", "T" 를 저장한다.
3. freinds와 크기가 같은 boolean형 배열 visited를 만들고 완전탐색 dfs()에 이용한다. dfs()는 friends를 for문을 돌면서 visited[i]가 false이면 String[i]를 true로 변경하고 String line에 추가하고 dfs()를 재귀호출 한 후에 visited[i]를 다시 false로 변경하여 dfs(깊이우선탐색)을 통해 모든 경우의 조합을 만들고 크기가 8이 되면 모든 카카오프렌즈가 나란히 일렬로 선 것이므로 조건 data를 for문을 돌면서 모든 조건에 맞는지 확인을 한다.
4. data의 각 글자를 charAt()을 이용하여 각각의 인덱스의 글자들을 가져오고 indexOf()를 이용하여 조건을 제시한 프렌즈와 상대방의 위치를 파악한다. 그리고 연산자('=' or '>' or '<')에 따라 프렌즈의 위치가 맞는지 확인한다. 조건을 제시한 프렌즈와 상대방의 위치 차를 Math.abs()를 이용하여 절대값을 구하고 data[i]의 마지막 인덱스인 숫자에 + 1을 하여 확인한다. 마지막 인덱스인 숫자는 중간에 있는 인원의 수를 뜻하는 것이기 때문에 + 1을 해주고 두 프렌즈의 위치 차와 비교한다.
5. 이렇게 조건 data를 for문을 돌면서 모두 통과하면 answer를 1씩 증가시키며 카운팅 하고 반환한다.