프로그래머스_단체사진 찍기(JAVA)

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

코딩테스트 연습 - 단체사진 찍기

단체사진 찍기

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100
• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

모든 조건을 만족하는 경우의 수를 리턴한다.

예제 입출력

n	data	answer
2	["N~F=0", "R~T>2"]	3648
2	["M~C<2", "C~M>1"]	0

예제에 대한 설명

첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.

두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.

---

[문제 풀이]

• public void comb(int num, String[] data) : 프렌즈가 설 수 있는 가능한 모든 조합을 구하는 함수
  • 백트래킹 이용
  • boolean[] v : 해당 인덱스의 프렌즈의 위치를 결정했는지 여부
  • ArrayList<Character> al : 프렌즈가 설 수 있는 조합을 저장하는 arraylist
  • HashSet<ArrayList<Character>> set: 프렌즈가 설 수 있는 모든 조합 중 조건을 만족하는 것만 저장할 set
  • 8명의 프렌즈 위치를 결정하는 조합을 완성할 때마다 조건을 만족하는지 여부를 검사하여 boolean ok에 저장한다. ok=true면 조건을 만족, ok=false면 조건을 만족하지 않음을 나타낸다.
    • 예를 들어 data[1] = N~F=0 이라고 하면, 
      • data 배열의 string에서 0번째 문자에 해당하는 프렌즈 N의 위치를 int idx1에 저장
      • data 배열의 string에서 2번째 문자에 해당하는 프렌즈 F의 위치를 int idx2에 저장
      • data 배열의 string에서 3번째 문자에 해당하는 연산자 '='를 char c에 저장
      • 두 프렌즈 사이에 존재하는 다른 프렌즈 수에 대한 조건을 나타내는 4번째 문자~끝까지에 해당하는 문자열을 int로 변경하여 int len에 저장한다.
    • c가 '='였다면, 두 프렌즈 사이에 존재하는 다른 프렌즈의 수는 정확히 len이어야 한다.
      • 위의 예시에서, N의 위치가 1, F의 위치가 2였다면, 두 프렌즈 사이에 존재하는 다른 프렌즈는 없다. 이 때 두 프렌즈의 거리인 Math.abs(idx1-idx2)는 1이고,  두 프렌즈 사이에 존재하는 다른 프렌즈는 0이다. 따라서 Math.abs(idx1-idx2)과 len+1이 같으면 조건을 만족하는 것이다.
      • Math.abs(idx1-idx2)!=len+1이면, 조건을 만족하지 않으므로 ok=false로 변경한 후 break;
    • c가 '>'였다면, 두 프렌즈 사이에 존재하는 다른 프렌즈의 수는 정확히 len보다 많아야 한다.
      • 예를 들어, R~T>2라고 하면, R과 T 사이에 존재하는 프렌즈의 수는 2명 보다 많아야하므로, 즉, 3명 이상이어야 한다.
      • R의 위치가 0, T의 위치가 4라고 한다면, 두 프렌즈 사이에는 4명의 프렌즈가 존재함을 의미하고, 두 프렌즈의 거리는 Math.abs(idx1-idx2) = 4가 된다. 즉 조건을 만족하기 위해 두 프렌즈 사이의 최소 거리는 len+2 이다.
      • Math.abs(idx1-idx2)<len+2이면, 조건을 만족하지 않으므로 ok=false로 변경한 후 break;
    • c가 '>'였다면, 두 프렌즈 사이에 존재하는 다른 프렌즈의 수는 정확히 len보다 적어야 한다.
      • 예를 들어, R~T<2라고 하면, R과 T 사이에 존재하는 프렌즈의 수는 2명 보다 적어야하므로, 즉, 1명 이하여야 한다.
      • R의 위치가 0, T의 위치가 2라고 한다면, 두 프렌즈 사이에는 1명의 프렌즈가 존재함을 의미하고, 두 프렌즈의 거리는 Math.abs(idx1-idx2) = 2가 된다. 즉, 조건을 만족하기 위해 두 프렌즈 사이의 최대 거리는 len이다.
      • Math.abs(idx1-idx2)>len이면, 조건을 만족하지 않으므로 ok=false로 변경한 후 break;
    • boolean ok의 값이 true라면 해당 순서는 조건을 만족하는 배치이다. 따라서 이를 set에 넣어준다.
• public int solution(int n, String[] data) : 메인 함수
  • 프렌즈의 수는 8이므로, boolean v의 크기는 8로 할당
  • 총 택할 프렌즈의 수는 8명 전부이므로 comb함수의 매개변수 num은 8로 설정
  • 최종 set의 size가 가능한 모든 조합의 수가 된다.

 

[코드]

import java.util.*;
class Solution {
    static boolean[] v;
    static char[] friend = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    static ArrayList<Character> al;
    static HashSet<ArrayList<Character>> set;
    public void comb(int num, String[] data){
        if(num==0){
            boolean ok = true;
            for(int i=0;i<data.length;i++){
                String str = data[i];
                int idx1 = al.indexOf(str.charAt(0));
                int idx2 = al.indexOf(str.charAt(2));
                char c = str.charAt(3);
                int len = Integer.parseInt(str.substring(4));
                
                if(c=='='){
                    if(Math.abs(idx1-idx2)!=len+1){
                        ok =false;
                        break;
                    }
                        
                }
                else if(c=='>'){
                    
                    if(Math.abs(idx1-idx2)<len+2){
                        ok=false;
                        break;
                    }
                }
                else if(c=='<'){
                    
                    if(Math.abs(idx1-idx2)>len){
                        ok=false;
                        break;
                    }
                }
                
            }
            if(ok){
                ArrayList<Character> temp = new ArrayList<>();
                temp.addAll(al);
                set.add(temp);
            }
            return;
        }
        for(int i=0;i<8;i++){
            if(!v[i]){
                v[i] = true;
                num-=1;
                al.add(friend[i]);
                comb(num, data);
                num+=1;
                v[i] = false;
                al.remove(al.indexOf(friend[i]));
            }
        }
        
    }
    public int solution(int n, String[] data) {
        int answer = 0;
        
        set = new HashSet<>();
        
        v = new boolean[8];
        al = new ArrayList<>();

        comb(8,data);

        answer = set.size();
        return answer;
    }
}