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

 

문제 

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

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

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력형식

입력은 조건의 개수를 나타내는 정수 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 > 1 , M~C < 2	0

 

풀이

100개가 넘는 규칙들을 살피며 되는 경우의 수는 만들기 어려움으로, 일단 모든 경우의 수를 만들어보고 아닌 것들을 제외하는 방식으로 접근하였다.

인원은 8명으로 한정되어 있으므로, 모든 순열의 가짓수는 8! 40320가지.

이때 최대 규칙의 수가 100가지, 각 규칙을 판단할때 친구 두명의 위치를 파악해야하므로 16번의 탐색

최대 40320X100X16 = 6451,2000번의 연산이 걸릴 것 같았는데.. 사실 딱히 다른방법이 생각나지 않아 그렇게 풀었다.

우선은 8명의 이니셜이 담겨있는 char형 배열의 모든 순열을 만드는데,

각 순열을 만들 때 마다 그 결과를 복사해서 (배열이라 주소를 그냥 넘겨버리면 소용이 없었다.)

넘겨준 순열을 각각의 규칙 (data)에 맞게 체크해서 아니면 answer--해주는 방식으로 진행하였다.

채점도 한가지 케이스에서만하고, 시간이나 메모리도 넉넉하게 주는 것 같다.

 

코드

class Solution {
	String[] data;
	int n;
	int answer = 1;
    public int solution(int n, String[] data) {
    	this.data = data;
    	this.n = n;
        char[] arr = {'A','C','F','J','M','N','R','T'};
        char[] result = new char[8];
        
        for(int i=2; i<=8; i++){
        	answer = answer * i;
        }
        System.out.println(answer);
        
        permutation(arr, 0, 8, 8, result);
        return answer;
    }
    
    public void permutation(char[] arr, int index, int n, int k, char[] result){
    	if(index == k){
    		for(int i=0; i<n; i++){
    			result[i] = arr[i];
    		}
    		check(result);
    	}
    	for(int i=index; i<n; i++){
    		swap(arr, index, i);
    		permutation(arr, index+1, n, k,result);
    		swap(arr, index, i);
    	}
    }
    
    public void check(char[] arr){
    	
    	for(int i=0; i<n; i++){
    		String rule = data[i];
    		
    		int indexof1 = find(arr,rule.charAt(0));
    		int indexof2 = find(arr,rule.charAt(2));	
    		int length = Math.abs(indexof1-indexof2)-1;
    		int range = rule.charAt(4)-48;
    		
    		switch(rule.charAt(3)){
    		
    		case '=' :{
    			if(length != range){
    				answer--;
    				return;
    			}
    			break;
    		}		
    		case '>' : {
    			if(range >= length) {
    				answer--;
    				return;
    			}
    			break;
    			}
    		case '<' : {
    			if(range <= length) {
    				answer--;
    				return;
    			}
    				break;
    			}
    		}
    	}
    }
    
    public void swap(char[] arr, int index, int i){
    	char temp = arr[index];
    	arr[index] = arr[i];
    	arr[i] = temp;
    }
    
    public int find(char[] arr, char s){
    	
    	for(int i=0; i<8; i++){
    		
    		if(arr[i] == s) {
    			return i;
    		}
    	}
    	return -1;
    }
}

 

결과