문제

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

코드

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
private static final int PEOPLE_COUNT = 8;
private static final String[] PEOPLE_NAMES = {"A", "C", "F", "J", "M", "N", "R", "T"};

private static int answer;
public int solution(int n, String[] data) {
    answer = 0;
    perm("", 0, new boolean[8], data);

    return this.answer;
}

private void perm(String perm, int depth, boolean[] isVisit, String[] data) {
    if (depth == PEOPLE_COUNT) {

        if (isCondition(perm, data)) {
            answer++;
        }
    }

    for (int i = 0; i < PEOPLE_COUNT; i++) {
        if (!isVisit[i]) {
            isVisit[i] = true;
            perm(perm + PEOPLE_NAMES[i], depth + 1, isVisit, data);
            isVisit[i] = false;
        }
    }
}

private boolean isCondition(String perm, String[] data) {
    boolean isCondition = true;

    for (int i = 0; i < data.length; i++) {
        char[] tochar = data[i].toCharArray();
        int people1 = perm.indexOf(tochar[0]);
        int people2 = perm.indexOf(tochar[2]);

        int interval = people1 > people2 ? people1 - people2 - 1 : people2 - people1 - 1;

        int requestInterval = tochar[4] - '0';
        if (tochar[3] == '=' && interval != requestInterval) {
            isCondition = false;
            break;
        }

        if (tochar[3] == '<' && interval >= requestInterval) {
            isCondition = false;
            break;
        }

        if (tochar[3] == '>' && interval <= requestInterval) {
            isCondition = false;
            break;
        }
    }

    return isCondition;
}

흐름

  1. {“A”, “C”, “F”, “J”, “M”, “N”, “R”, “T”}로 나올 수 있는 문자열을 모두 만들어서 비교
  2. 위 array size 만큼 돌면서 문자열을 만드는데 이미 문자열에 포함된 문자는 추가하지 않기 위해 똑같은 size에 boolean array를 만듬
  3. 만들어서 그 boolean array의 index가 true면 이미 문자열에 추가된 문자 이므로 넘어감
  4. 문자열에 추가되지 않은 문자라면 다시 추가하지 않기 위해 boolean을 true로 변경
  5. 문자열을 이어 붙이기 위해 현재 메서드(perm)를 재귀호출 하는데
  6. 현재 문자열(perm)에 추가할 문자 (PEOPLE_NAMES[i])를 더하고, 배열 인덱스가 한 단계 깊어 졌으므로 depth를 +1 해서 호출
  7. 반복 하다가 사람 수 만큼(PEOPLE_NAMES) 들어왔으면
  8. 이 문자열이 비교와 할 문자열의 조건과 같은지 확인함
  9. {“NF=0”, “RT>2”} 이런 식으로 되어 있으므로
  10. 조건 문자열에서 먼저 0번째와 2번째를 가져와서 지금 만든 문자열에서 해당 문자들이 몇 번째에 위치해 있는지 구함 (indexOf())
  11. 구한 값의 차를 구함
  12. 조건에서 해당 문자들의 간격이 몇인지 알기 위해 4번째 문자를 가져옴
  13. 조건 문자열에서 3번째 문자에 따라 참인지 아닌지 비교함
    1. ‘=’ 이면서 구한 간격과 조건의 간격이 같지 않으면 false
    2. ‘<’ 이면서 구한 간격이 조건의 간격보다 크거나 같으면 false
    3. ‘>’ 이면서 구한 간격이 조건의 간격보다 작거나 같으면 false
  14. 모든 조건을 통과하면 경우의 수를 증가시킴
  15. 모든 문자열에 대해 비교가 끝나면 끝

부연 설명 boolean[] isVisit의 변화와 문자열이 만들어지는 과정

1
2
3
4
5
6
7
for (int i = 0; i < PEOPLE_COUNT; i++) {
    if (!isVisit[i]) {
        isVisit[i] = true;
        perm(perm + PEOPLE_NAMES[i], depth + 1, isVisit, data);
        isVisit[i] = false;
    }
}
  1. {false, false, false, false, false, false, false, false} 인 상태에서 위 반복을 돌면서 재귀로 들어감
  2. {true, false, false, false, false, false, false, false}가 된 상태에서 perm 재귀를 타고 반복…
  3. {true, true, true, true, true, true, true, true}이 된 상태로 재귀를 빠져나옴
  4. 빠져나오면 isVisit[i] = false 때문에 마지막 7번째 index는 false로 변경되고 반복문이 끝났으므로 재귀를 빠져나옴
  5. 재귀를 나왔으니 {true, true, true, true, true, true, true, false}인 상태에서 i는 6이고 6번째 index도 false로 만듬
  6. {true, true, true, true, true, true, false, false} 그럼 이 상태가 되고 여기서 반복문이 돌아서 i는 7이 되고 7번째 index는 true로 변경
  7. {true, true, true, true, true, true, false, true}인 상태로 재귀에 들어가지만 depth가 8이 아니므로 다시 for문을 도는데
  8. {true, true, true, true, true, true, false, true}인 상태이므로 여태 재귀돌면서 만들었던 문자열 마지막에 6번째 문자가 추가되게 됨
    1. “ACFJMNT” + 6번째 index인 “R”
  9. 위 상황이 반복되면서 8자리 문자열이 계속 반복적으로 생성되고 비교됨

결과

번호 속도
테스트 1 통과 (1723.16ms, 333MB)

테스트 케이스

1
2
assertEquals(3648, test.solution(2, new String[] {"N~F=0", "R~T>2"}));
assertEquals(0, test.solution(2, new String[] {"M~C<2", "C~M>1"}));

참고 사이트