프로그래머스 : 단체사진 찍기 (Java)

🔗 문제 링크

 

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

---

📖 풀이 과정

- 브루트 포스 유형의 문제입니다. 

- 문제의 흐름은 다음과 같습니다.

  - 먼저 재귀를 이용해 모든 경우의 수를 구합니다.
  
  - 구한 경우마다 조건에 충족하면 answer + 1, 그렇지 않으면 answer 변수를 그대로 둡니다.
  
- 그렇기에 먼저 모든 경우를 구하는 것부터 시작해야 합니다.

  - 저는 재귀를 이용해 구했습니다.
  
  - visited라는 boolean 1차원 배열을 선언했으며 for문을 돌면서 체크했습니다.
  
- 조건을 확인하는 메소드는 다음과 같습니다.

  - 각 위치는 고정적입니다.(의미도 고정)
  
  - 그러므로 charAt() 메소드를 이용해서 간격을 구합니다.
  
  - 여기서! 두가지를 주의해야 합니다.
  
    - 첫째는 절대값으로 계산을 해야하는 것
    
    - 둘째는 standard 변수에 1을 더해줘야 합니다.
    
      - 그 이유는 pos1,2 값이 3과 4일 경우 빼면 값은 1입니다.
      
      - 하지만 문제에서 정의한 간격은 사이에 있는 프렌즈의 수이기 때문에 standard에 1을 더한 값과 비교해야 합니다.
      
  - 마지막으로 재귀 메소드에 idx 변수를 두어, 8이 되었을 때 종료를 하게 합니다.

---

💻 코드

public class Solution {
	static int answer;
	static boolean[] visited;
	static String[] arr = {"A","C","F","J","M","N","R","T"};
	
	public static int solution(int n, String[] data) {
		answer = 0;
		visited = new boolean[8];
		
		dfs(0,"",data);
		return answer;
	}
	
	private static void dfs(int idx, String names,String[] data){
		if(idx == 8){
			if(check(names,data)) {
				answer += 1;
			}
			return;
		}
		
		for(int i = 0; i< 8; i++){
			if(!visited[i]){
				visited[i] = true;
				String name = names + arr[i];
				dfs(idx + 1,name,data);
				visited[i] = false;
			}
		}
	}
	
	private static boolean check(String name,String[] data){
		for(String str : data){
			int pos1 = name.indexOf(str.charAt(0));
			int pos2 = name.indexOf(str.charAt(2));
			
			char logic = str.charAt(3);
			int standard = str.charAt(4) - '0';
			
			switch (logic){
				case '=' :
					if(!(Math.abs(pos1 - pos2) == standard + 1)){
						return false;
					}
					break;
				case '>' :
					if(!(Math.abs(pos1 - pos2) > standard + 1)){
						return false;
					}
					break;
				case '<' :
					if(!(Math.abs(pos1 - pos2) < standard + 1)){
						return false;
					}
					break;
			}
		}
		return true;
	}
}