프로그래머스_1835_단체사진 찍기

📖 목차

👆 링크
🤞 문제
👌 코드
🖖 풀이
🖐 Git gist 주소

📌 링크

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

📝 문제

  카카오프렌즈 캐릭터가 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 서야 한다. 그런데 네오는 프로도와 나란히 서기를 원하고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원한다.

  각 캐릭터가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

💻 코드

package programmers_1835_takeAGroupPhoto;
import java.util.*;
/*
 * 
 * 프로그래머스
 * 1835. 단체사진 찍기
 * https://programmers.co.kr/learn/courses/30/lessons/1835
 * 2021-05-13
 * 
 * */
class Solution {
	static String[] condition;
	static int answer = 0;
	static boolean visited[];
	static Map<Character, Integer> friends;
	static Map<Integer, Integer> line;
	
    public int solution(int n, String[] data) {
    	answer = 0;
        visited = new boolean[8];
        friends = new HashMap<>();
        line = new HashMap<>();
        
        condition = data;
        
        friends.put('A', 0);
        friends.put('C', 1);
        friends.put('F', 2);
        friends.put('J', 3);
        friends.put('M', 4);
        friends.put('N', 5);
        friends.put('R', 6);
        friends.put('T', 7);
        
        dfs(0);
        
        return answer;
    }

	private void dfs(int order) {
		if(order == 8) {
			if(checkLogic()) answer++;
			return;
		}
		
		for(int identity = 0; identity < 8; identity++) {
			if(!visited[identity]) {
				line.put(identity, order);
				visited[identity] = true;
				dfs(order + 1);
				visited[identity] = false;
			}
		}
	}

	//조건체크 메소드
	private boolean checkLogic() {
		//데이터 추출
		for(String data : condition) {
			int obj1 = friends.get(data.charAt(0));
			int obj2 = friends.get(data.charAt(2));
			int order1 = line.get(obj1); //obj1의 순서
			int order2 = line.get(obj2); //obj2의 순서
			
			char op = data.charAt(3);
			int value = data.charAt(4)-'0' + 1;
			
			if(op == '=') {
				if(Math.abs(order1 - order2) != value) return false;
			}else if(op == '<') { //미만
				if(Math.abs(order1 - order2) >= value) return false;
			}else { //초과
				if(Math.abs(order1 - order2) <= value) return false;
			}
		}
		return true;
	}
}

✍ 풀이

👉 모든 경우의 수를 돌며, 해당 line이 조건에 맞는지 체크한다.

모든 경우의 수가 8! = 40,320 이기 때문에 완전 탐색으로 푸는 것이 가능하다.

1. 주어지는 문자열에서 데이터를 어떻게 파싱할 것인가?

👉 Map 객체로 각 캐릭터에 매칭되는 Character 와 Integer 를 저장하고, 문자열을 읽으며 해당 Character 에 매핑되는 Integer 값으로 파싱한다.

▼ friends에 각 캐릭터의 문자형과 숫자형을 저장한다.

friends.put('A', 0);
friends.put('C', 1);
friends.put('F', 2);
friends.put('J', 3);
friends.put('M', 4);
friends.put('N', 5);
friends.put('R', 6);
friends.put('T', 7);

• Map<Character, Integer> friends
  
  

  Key	Value
  A	0
  C	1
  F	2
  J	3
  M	4
  N	5
  R	6
  T	7

      Value는 각 문자를 Integer형으로 구분하기 위한 숫자이다.

❓ 굳이 숫자형으로 저장하는 이유
A C F J M N R T 를 반복문으로 돌리기 위해서는 숫자형이어야 편하기 때문이다.


❓ 굳이 Map에 저장 안해도 되지 않나
맞다.

char[] friends = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};

배열로 풀어도 무관하다.

▼ 0~7번째에 설 캐릭터를 정한다.

private void dfs(int order) {
	if(order == 8) {
		if(checkLogic()) answer++;
		return;
	}
		
	for(int identity = 0; identity < 8; identity++) {
		if(!visited[identity]) {
			line.put(identity, order);
			visited[identity] = true;
			dfs(order + 1);
			visited[identity] = false;
		}
	}
}

• dfs(int order)로 0부터 7까지 돌며, line에 identity와 order를 저장한다.
  
  order : n번째 순서에
  identity : 어떤 캐릭터가 서있는지
  💡 identity = 7, order = 0 이라면 맨 0번째에 T(7)가 선다.
  
  

• for문으로 n번째 순서에 올 수 있는 캐릭터의 모든 경우의 수를 탐색한다.

• 중복방지를 위해 visited로 체크해준다.
  해당 재귀함수를 빠져나온 후엔 다시 visited를 해제해준다.

• order=8 일 시, 8명 캐릭터 모두 일렬로 서있기 때문에 checkLogic()함수로 주어진 조건에 맞는 상태인지 확인한다.
  
  
  

▼ data = (obj1)~(obj2)(op)(value)

• 주어진 문자열에서 각각의 요소를 추출한다.

for(String data : condition) {
	int obj1 = friends.get(data.charAt(0));
	int obj2 = friends.get(data.charAt(2));
	int order1 = line.get(obj1); //obj1의 순서
	int order2 = line.get(obj2); //obj2의 순서
			
	char op = data.charAt(3);
	int value = data.charAt(4)-'0' + 1;
    	...

  data가 N~F=0일 경우
 data.charAt(0)은 N , data.charAt(2)는 F 이다.
 friends에서 Key가 N인 int형 데이터를 찾아 obj1에 넣는다.

 💡 즉, obj1과 obj2는 카카오프렌즈를 int타입으로 바꾼 변수이다.

2. 조건의 두 캐릭터가 서로 얼마나 떨어져 있는지 어떻게 알까?

👉 두 캐릭터의 순서를 뺀 절대값으로 알 수 있다.

▼ 조건을 만족하지 않으면 false를 리턴하는 식으로 검사한다.

if(op == '=') {
	if(Math.abs(order1 - order2) != value) return false;
    
}else if(op == '<') { //미만
	if(Math.abs(order1 - order2) >= value) return false;
    
}else { //초과
	if(Math.abs(order1 - order2) <= value) return false;
}

❗ 주의할 점

전역변수의 초기화를 solution 안에서 해주어야 정답처리가 된다.
이유는 잘 모르겠다 ㅠ

👩‍💻 Git gist 주소

https://gist.github.com/ysyS2ysy/c91676d2fa524ff807081c7f4df1f4ae