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

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

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

class Solution {
		int answer;
	    public int solution(int n, String[] data) {
	        answer = 0;
	        String friends= "ACFJMNRT";
	        solve(friends,n,data);
	        return answer;
	    }

		private int solve(String friends, int n, String[] data) {
			boolean visited[] = new boolean[friends.length()];
			char permuArr[] = new char[friends.length()];
			permutation(visited,permuArr,friends,n,data,0);
			return 0;
		}

		private void permutation(boolean[] visited, char[] permuArr, String friends, int n, String[] data, int cnt) {
			if(cnt==friends.length()) {
				if(conditionCheck(String.valueOf(permuArr),data,n)) answer++;
//				System.out.println(Arrays.toString(permuArr));
				return;
			}
			
			for(int i=0; i<friends.length(); i++) {
				if(visited[i]) continue;
				permuArr[cnt]=friends.charAt(i);
				visited[i]=true;
				permutation(visited, permuArr, friends, n, data, cnt+1);
				visited[i]=false;
			}
		}

		private boolean conditionCheck(String permuResult, String[] data, int n) {
			for(int i=0; i<n; i++) {
				String condition = data[i];
				int firstFriend=permuResult.indexOf(condition.charAt(0));
				int secondFriend=permuResult.indexOf(condition.charAt(2));
				if(!distanceCheck(firstFriend, secondFriend, condition.charAt(3),condition.charAt(4))) return false;
			}
			return true;
		}

		private boolean distanceCheck(int firstFriend, int secondFriend, char condition, char distance) {
			switch(condition) {
			case '>':
				if(Math.abs(firstFriend-secondFriend)-1>distance-'0') return true;
				return false;
			case '<':
				if(Math.abs(firstFriend-secondFriend)-1<distance-'0') return true;
				return false;
			case '=':
				if(Math.abs(firstFriend-secondFriend)-1==distance-'0') return true;
				return false;
			}
			return false;
		}
	}

소요시간 : 34분

 

로직을 살펴보면 

 

1. 순열을 통해서 모든 경우의 수를 구해준다. - permutation()

2. 하나의 순열에 대해서 모든 data를 순회하면서 모든 조건에 부합하는지 확인해준다.

  - conditionCheck() -> 조건에 해당하는 두 사람이 현재 순열에서 몇번에 있는지 뽑아내준다

  - distanceCheck() -> conditionCheck()에서 뽑은 두 사람의 인덱스를 통해 거리를 계산해준다.

 

우선 이 로직의 시간복잡도를 구해보자면

순열 8! , data의 길이 100이므로 시간은 충분하다!

 

정말 문제에서 시키는 그대로만 하면 되는 문제이기 때문에 안의 코드는 딱히 설명할 필요가 없을 것 같다.

 

끝~