알고리즘 풀이/프로그래머스

[프로그래머스][JAVA] 단체사진 찍기 (순열)

배게 2021. 10. 28. 14:17
728x90

처음에는 백트래킹으로 하려고 했는데

순열을 전부 짜 놓은 다음에 해결하는 것이 훨씬 간편하기도 하고

백트래킹으로 불가능한지 아닌지는 잘 모르겠으나 조건상 어려워 보였음

 

순열 짜기 -> 짠 순열이 문제에서 주어진 Data(조건)을 전부 만족시키면 answer++(count)

 

 

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.*;
 
class Solution {
    String[] data;
    int n;
    List<Character> comb;
    boolean[] lined;
    List<Character> friendsList;
    int answer;
    
    private boolean checkData(){
        
            
        for(String d : data){
            char friend1 = d.charAt(0);
            char friend2 = d.charAt(2);
 
            int index1 = comb.indexOf(friend1);
            int index2 = comb.indexOf(friend2);
 
            int interval = (int)Math.abs(index1-index2)-1;
 
            char sign = d.charAt(3);
            int intervalCond = d.charAt(4)-'0';
 
            if(sign=='=' && interval==intervalCond){
                continue;
            }
            else if(sign=='<' && interval<intervalCond){
                continue;
            }
            else if(sign=='>' && interval>intervalCond){
                continue;
            }
            else{
                return false;
            }
        }          
        
        return true;
    }
    
    private void permutation(int pos){
        if(pos==8){
            if(checkData()){
                answer++;    
            }
            return;
        }
        
        for(int i=0; i<lined.length; i++){
            if(!lined[i]){
                comb.add(friendsList.get(i));
                lined[i] = true;    
                
                permutation(pos+1);
                
                comb.remove(pos);
                lined[i] = false;
            }      
        }
 
        
    }
    
    public int solution(int nInput, String[] dataInput) {
        data = dataInput;
        n = nInput;
        comb = new ArrayList<>();
        lined = new boolean[8];
        friendsList = Arrays.asList('A','C','F','J','M','N','R','T');
        answer = 0;
        
        permutation(0);
 
        
        
        
        return answer;
    }
}
cs