📖 목차
👆 링크
🤞 문제
👌 코드
🖖 풀이
🖐 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형으로 구분하기 위한 숫자이다.
❓ 굳이 숫자형으로 저장하는 이유
ACFJMNRT를 반복문으로 돌리기 위해서는 숫자형이어야 편하기 때문이다.
❓ 굳이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
