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

https://school.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 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

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

예제 입출력

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

 

 

#알고리즘

순열

완전탐색

 

#난이도

level 2

 

#풀이방법

이 문제에서 중요한 포인트는 특정 캐릭터들이 카메라 앞에 한줄로 선다는 것이다. 이것만 봐도 아 순열이구나 싶을 것이다. 순열이면 바로 dfs/백트래킹으로 모든 경우의 수를 탐색한 후, 매개변수로 조건에 맞는 것들을 차례로 확인하여 

조건에 모두 부합하면 answer++을 하는식으로 풀이하였다.

 

public static void backTrack(String line,int idx,boolean[] visited,String[] data) {
         
         if(idx == 8) {
             //조건에 맞는지 체크
             if(check(line,data))
                 answer++;
             
             return;
         }//캐릭터가 모두 나란히 섰을 경우, check후 return
         
         
         for(int i=0; i<character.length; i++) {
             
             if(!visited[i]) {
                 
                 visited[i] = true;
                 backTrack(line+character[i],idx+1,visited,data);
                 visited[i] = false;
                 
             }
    
         }
         
        
     }

 

백트래킹을 이용하여 모든 캐릭터들이 줄을 서는 경우의 수를 조사한 후 Check()로 넘어가 확인한다.

 

 public static boolean check(String line,String[] data) {
         
         for(int i=0; i<data.length; i++) {
            
             int s1 = line.indexOf(data[i].charAt(0));
             int s2 = line.indexOf(data[i].charAt(2));
             int dis = Math.abs(s1-s2);//s1과 s2의 거리
             //매개변수로 주어지는 data를 파싱
             
             if(data[i].charAt(3) == '=') {
                     
                 if(dis != data[i].charAt(4)-'0'+1)
                     return false;
                 
             }
             else if(data[i].charAt(3) == '<') {
                
                 if(dis >= data[i].charAt(4)-'0'+1) {
                     return false;
                 }
                 
             }
             else {
                 
                 if(dis <= data[i].charAt(4)-'0'+1) {
                     return false;
                 }
                
             }
             
         }
         
         return true;
         
     }//여기서 확인한다.

 

매개변수로 주어지는 string[] data를 파싱하여, 각각 =,<,>으로 나누고, String line에 data에 주어지는 캐릭터들의 위치를 파악하고 그 거리가 조건에 부합하지 않으면 false를 반환 or 모든 조건에 부합한다면 true를 반환하여  true인 경우 answer++로 경우의 수를 세준다.

 

#전체 코드

 

import java.util.*;
//2t
 
public class Solution {
    
     static int answer;
     static Character[] character = {'A','C','F','J','M','N','R','T'};
     //캐릭터들 
     
     public static int solution(int n,String[] data) {
          
         boolean[] visited = new boolean[8];
         
         answer = 0;
         backTrack("",0,visited,data);
         
         return answer;
         
     }
     
     public static void backTrack(String line,int idx,boolean[] visited,String[] data) {
         
         if(idx == 8) {
             //조건에 맞는지 체크
             if(check(line,data))
                 answer++;
             
             return;
         }//캐릭터가 모두 나란히 섰을 경우, check후 return
         
         
         for(int i=0; i<character.length; i++) {
             
             if(!visited[i]) {
                 
                 visited[i] = true;
                 backTrack(line+character[i],idx+1,visited,data);
                 visited[i] = false;
                 
             }
    
         }
         
        
     }
     
     public static boolean check(String line,String[] data) {
         
         for(int i=0; i<data.length; i++) {
            
             int s1 = line.indexOf(data[i].charAt(0));
             int s2 = line.indexOf(data[i].charAt(2));
             int dis = Math.abs(s1-s2);//s1과 s2의 거리
             //매개변수로 주어지는 data를 파싱
             
             if(data[i].charAt(3) == '=') {
                     
                 if(dis != data[i].charAt(4)-'0'+1)
                     return false;
                 
             }
             else if(data[i].charAt(3) == '<') {
                
                 if(dis >= data[i].charAt(4)-'0'+1) {
                     return false;
                 }
                 
             }
             else {
                 
                 if(dis <= data[i].charAt(4)-'0'+1) {
                     return false;
                 }
                
             }
             
         }
         
         return true;
         
     }//여기서 확인한다.
     
 
}