가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.
입력 형식
입력은 조건의 개수를 나타내는 정수n과n개의 원소로 구성된 문자열 배열data로 주어진다.data의 원소는 각 프렌즈가 원하는 조건이N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.
- 1 <= n <= 100
- data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
- 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다.{A, C, F, J, M, N, R, T}각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
- 두 번째 글자는 항상~이다.
- 네 번째 글자는 다음 3개 중 하나이다.{=, <, >}각각 같음, 미만, 초과를 의미한다.
- 다섯 번째 글자는0이상6이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.
출력 형식
모든 조건을 만족하는 경우의 수를 리턴한다.
예제 입출력
| 2 |
["N~F=0", "R~T>2"] |
3648 |
| 2 |
["M~C<2", "C~M>1"] |
0 |
예제에 대한 설명
첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.
두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.
모든 조건을 만족하는지 확인하기 위해서는 완전 탐색을 해야한다고 생각했고,
8개의 캐릭터가 줄을 설 수 있는 방법은 8! = 40320 가지가 나와서 충분히 완전 탐색을 하면 되겠다라고 생각했다.
DFS(깊이 우선 탐색)으로 순서(01234567 ~ 76543210)를 정하고, 조건들을 확인하고 모든 조건을 만족하면 경우의 수 1을 리턴한다
순서를 정할때는 문자열(숫자)로 저장하고, 각 문자(숫자)는 ID 배열의 인덱스이다
입력(조건)을 받을 때는 캐릭터들의 이니셜을 문자 타입으로 받기 때문에, Map 타입을 통해 캐릭터 이니셜과 현재 위치(인덱스)를 매핑해줬다
캐릭터들의 위치를 배열로 저장하게 된다면, 입력 조건을 확인할 때마다 2개의 캐릭터의 위치를 확인하기 위해서 O(N)의 시간복잡도를 가지지만, Map 타입을 사용하게 된다면 O(1) 시간복잡도만으로 위치를 찾을 수 있기 때문에 좀 더 효율적이지 않을까 생각했다
내 코드 진단 & 생각
- 캐릭터들의 순서가 정해졌는지 저장하는 boolean 배열 객체를 dfs 실행마다 생성하여 다음 dfs 함수로 넘기지 않는다. (당연히 메모리 낭비니까?..) 전역변수(boolean 배열 b)로 선언하여 true/false 변경하며 백트래킹을 사용함. 그래도 전역 변수를 사용하지 않고 solution 함수에 boolean 배열 객체를 선언하여 dfs 매개 변수에 추가했으면 좀 더 깔끔한 코드가 되지 않았을까?
- Map도 전역 변수로 선언하여, dfs 안에서 객체 생성을 하지 않고, clear()를 통해 재사용했는데 위 생각처럼 dfs 매개 변수에 추가하면 더 좋은 코드가 됐을 것 같다. (ID 배열도 마찬가지). 그런데 dfs 안에서 Map 객체를 생성했더라도 Map 데이터 쌍 ('A',0), ('C',1) 들도 map.put 할 때마다 기본형 타입이 아닌 객체로 저장되니 이러나 저러나 3가지 방식 모두 메모리 상으론 비슷하지 않을까?
- 백준 사이트 같았으면 결과값(answer)도 전역으로 선언하고, void dfs() 해서 풀었을텐데, 프로그래머스는 제출 방식이 다르다보니 int dfs()로 경우의 수를 리턴하여 answer에 더하는 방식으로 풀어봤다.
import java.util.HashMap;
import java.util.Map;
class Solution {
char[] ID = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
boolean[] b = new boolean[8];
Map<Character, Integer> map = new HashMap<Character, Integer>();
int dfs(String[] data, int depth, String order) {
if (depth == 8) {
map.clear();
for (int i = 0; i < order.length(); i++) {
map.put(ID[order.charAt(i) - '0'], i);
}
for (int i = 0; i < data.length; i++) {
int dist = Math.abs(map.get(data[i].charAt(0)) - map.get(data[i].charAt(2))) - 1;
int cpVal = data[i].charAt(4) - '0';
char sign = data[i].charAt(3);
if (sign == '>') {
if (dist <= cpVal)
return 0;
} else if (sign == '<') {
if (dist >= cpVal)
return 0;
} else {
if (dist != cpVal)
return 0;
}
}
return 1;
}
int ret = 0;
for (int i = 0; i < 8; i++) {
if (b[i])
continue;
b[i] = true;
ret += dfs(data, depth + 1, order + i);
b[i] = false;
}
return ret;
}
public int solution(int n, String[] data) {
int answer = 0;
answer += dfs(data, 0, "");
return answer;
}
}
