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

문제 보러 가기

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

이 문제는 카카오프렌즈들을 세우는 순서의 경우의 수 -> 순열을 구하는 문제였다! 순열을 다 구하면 시간 초과가 날까 고민했지만 그냥 모든 순열을 구해서 풀었다.

 

하지만 제출 시 틀리다고 나와서 뭐가 문제인지 계속 고민했는데,,, 전역 변수의 경우 main안에서 초기화를 꼭 해줘야 한다... 왜지.. 궁금하다.. 이걸로 삽질하지 말자고 올리는 풀이! -프로그래머스는 다 그런 듯..?

 

 

 

문제풀이

-8명을 세우는 총경우의 수는 8! = 40320 이것을 최대 답의 수로 초기화한다

-카카오프렌즈에 해당하는 알파벳 8 개를 배열에 넣고 permutation()를 통해 String을 구한다

-주어진 data []에서 구해진 String이 조건에 맞는지 확인하고 맞지 않다면 ans--로 답 개수를 줄여준다

 

 

 

 

class Solution {
	static Condition[] cData;
	static int ans;
    public int solution(int n, String[] data) {
   	    cData = new Condition[n];
        ans=1;
		for(int i=2;i<=8;i++) {
			ans *= i;
		}
		
		for(int i=0;i<n;i++) {
			String s1 = data[i].substring(0, 1);
			String s2 = data[i].substring(2,3);
			char op = data[i].charAt(3);
			int num = (data[i].charAt(4)-'0');
			cData[i] = new Condition(s1,s2,op,num);
		}
		String[] arr = {"A","C","F","J","M","N","R","T"};
		permutation(arr,0,arr.length,arr.length);
		return ans;
	}
	static boolean check(String s) {
		
		for(int i=0;i<cData.length;i++) {
			Condition c= cData[i];
            //순열함수로 구해진 String에서 각자 조건에 해당하는 문자의 인덱스 거리구함
			int idx = Math.abs(s.indexOf(c.s2)-s.indexOf(c.s1));
            //조건에 해당하는지 검사
			switch (c.op){
				case '=':
					if(idx!=c.num+1) {
						return false;
					}
					break;
				case '<':
					if(idx>=c.num+1) {
						return false;
					}
					break;
				case '>':					
					if(idx<=c.num+1) {
						return false;
					}
					break;
			}
		}
		return true;
	}
    //8개 알파벳 순열구함
	static void permutation(String[] arr, int depth, int n, int r) {
	    if (depth == r) {
	        StringBuilder sb = new StringBuilder();
	        for(int i=0;i<r;i++) {
	        	sb.append(arr[i]);
	        }
            //조건에 해당하지 않아 false return 받으면 답 줄여줌
	        if(!check(sb.toString())) {
	        	ans--;
	        }
	    	return;
	    }
	 
	    for (int i=depth; i<n; i++) {
	        swap(arr, depth, i);
	        permutation(arr, depth + 1, n, r);
	        swap(arr, depth, i);
	    }
	}
	 
	static void swap(String[] arr, int depth, int i) {
	    String temp = arr[depth];
	    arr[depth] = arr[i];
	    arr[i] = temp;
	}

}
class Condition{
	String s1;
	String s2;
	char op;
	int num;
	
	Condition(String s1,String s2,char op,int num){
		this.s1 = s1;
		this.s2 = s2;
		this.op = op;
		this.num = num;
	}
}