👀 문제
https://programmers.co.kr/learn/courses/30/lessons/1835
👊 도전
1. 설계
- char[]로 알파벳을 다 넣는다.
- DFS로 순열을 구한다. visit[8], perm[8] 이용
- idx==8이면 isPossible()로 조건 만족하는지 체크한다.
- 맞으면 cnt++한다.
isPossible() - data[i]의 a, b, cond, num을 뽑는다.
- perm[]에서 a, b의 위치를 찾는다. for문 이용
- 두 인덱스 사이의 거리 gap을 구한다.
- gap이 조건을 만족하지 않으면 false를 리턴한다
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;
/**
*
* @author HEESOO
*
*/
class Solution {
char[] alpha={'A','C','F','J','M','N','R','T'};
boolean[] visit;
char[] perm;
int cnt;
public int solution(int n, String[] data) {
int answer = 0;
visit=new boolean[8];
perm=new char[8];
cnt=0;
permutate(0, data);
return cnt;
}
public void permutate(int idx, String[] data){
if(idx==8){ // 순열 생성 완료
if(isPossible(data)) cnt++; // 조건 맞으면 cnt++
return;
}
for(int i=0;i<8;i++){
if(visit[i]) continue; // 중복 제거
// i를 지금 사용하는 경우
visit[i]=true;
perm[idx]=alpha[i];
permutate(idx+1, data); // 재귀로 다음 값 찾기
// i를 지금 사용하지 않는 경우
visit[i]=false;
}
}
public boolean isPossible(String[] data){
for(String d:data){
char a=d.charAt(0);
char b=d.charAt(2);
char cond=d.charAt(3);
int num=d.charAt(4)-'0';
// perm에서 a, b의 위치(인덱스) 찾기
int aIdx=0, bIdx=0;
for(int i=0;i<8;i++){
if(perm[i]==a) aIdx=i;
if(perm[i]==b) bIdx=i;
}
// 두 지점의 거리 계산 및 조건 체크
int gap=Math.abs(aIdx-bIdx)-1;
if(cond=='=' && gap!=num) return false;
else if(cond=='<' && gap>=num) return false;
else if(cond=='>' && gap<=num) return false;
}
return true;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 순열을 이용하여 모든 경우의 수를 구한다
- permutate()의 파라미터 idx는 perm[]에 삽입할 인덱스 위치이다.
- idx==8이라는 뜻은 순열 생성이 완료되었다는 뜻이므로 isPossible()을 이용하여 조건을 체크한다.
- isPossible()이 T라면 그 순열은 사용 가능한 것이므로 cnt++한다.
- 아닐 경우 for문을 돌며 사용한 값이면 패스하고(visit[i]), 아닐 경우 i번째 값을 사용하는 경우, 그렇지 않은 경우로 나누어 작성한다.
- 만든 순열이 조건을 만족하는지 체크한다
- data[]의 경우를 모두 만족해야 하므로, 체크하다가 중간에 틀린 것이 있으면 바로 false를 리턴하고 종료한다.
- char a, b, cond, int num에 조건을 뽑아 저장한다.
- 생성한 perm[]에서 a, b의 위치를 찾는다. 두 개의 간격을 계산하기 위함이다. for문을 이용한다.
- gap에 간격을 저장한다. 이때 a, b가 바로 붙어있다면 간격은 0이 되어야 하므로 -1을 해준다.
- cond를 체크하고, gap과 num이 cond에 어긋난다면 false를 리턴한다.
- 모두 일치한다면 true를 리턴한다.